\chapter{面向大规模众包数据的隐私保护统计分析方案}


众包是大规模多源数据收集和统计分析的有效方法。而对用户隐私的高度关注推动了保护隐私的统计分析方法的发展。本研究为众包场景提出了一个安全高效的隐私保护的统计分析方案。本方案融合采用广泛使用的密态计算技术——同态加密和安全两方计算，来设计安全的统计分析框架，保障了强大的加密安全性。本方案引入了使用直方图进行统计分析的创新算法，包括分位数估计、离群值消除、为卡方检验构建列联表和曼-惠特尼\textit{U}检验等功能。随着数据量的规模增大，这些算法只会有很小的开销增长，因此非常适合处理大量用户数据。此外，通过密钥分离设计，本方案保证了即使在数据密文可能暴露的情况下，也只有请求者才能独立解密最终结果。通过全面和有针对性的实验，本方案的安全性、效率和可扩展性得到了充分的验证。

\section{引言}

% 相比于基本的数据聚合和真值发现任务，对于多源数据进行统计分析同样也是重要的应用需求。常见的统计分析方法，例如方差、最大值、最小值、直方图、分位数（中位数、上四分位数、下四分位数），以及假设检验问题，例如卡方检验、秩和检验等，都是对数据进行更有效的分析挖掘的工具。面向多源大数据，这些统计分析方法往往可以发挥更重要的应用价值，然而同样地， 用户数据隐私泄露的风险也随之变大，如何保护数据隐私在统计分析过程中不被泄露是急需解决的问题。此外，多种统计分析方法往往也具有组合使用需求，这相比于基本的数据聚合和真值发现任务带来了更多挑战，也即如何在保护数据和中间过程隐私的同时，提供多种统计分析功能的可组合性。

% 此外，随着多源大数据规模不断扩张，其中难以避免包含一些与大多数数据的特征不一致的异常数据。出现数据异常的情况实际上很常见，比如数据收集时设备的故障、主观因素的影响、或者存在估计提交无效数据的不诚实的数据源等因素都有可能导致异常数据的产生。这些由于各种错误产生的异常数据对数据后续分析处理带来了不利影响，有可能需要提前识别并筛除出去。对于隐私保护的数据而言，采用高效的隐私保护统计分析方法也可以实现一些常见的检测和筛除异常数据的算法。

% ---------------------------------------------------------------------------



随着移动互联网技术的高速发展，数据量呈现出爆炸式增长，催生了众包计算模式的兴起。这些模式使得用户（数据拥有者）能够利用自身设备轻松参与众包任务，大幅扩展了众包数据的规模。对这些多源海量数据，可以利用统计方法进行汇总分析，以获取有价值的信息。然而，亲自从大量用户那里收集和分析数据存在着巨大的存储、计算和通信开销，在实际中并不可行。为解决这一问题，基于第三方云服务的众包模式越来越受关注，它提供了一种低成本、高效、可扩展的可行解决方案。但云服务平台可信性对用户和请求者（任务发起方）来说仍然是一大担忧，数据隐私保护问题首当其冲。用户数据可能包含个人敏感信息，如果未经适当保护就提供给不受信任的众包服务提供商，可能导致严重的隐私泄露。对隐私的担忧也会阻碍用户参与众包任务，从而妨碍众包的发展。此外，如果众包任务结果未获充分保护，请求者也可能面临经济损失风险。对于众包任务的请求者而言，他们往往需要为发起任务而支付相关费用，分析的结果也具备经济价值，因此请求者希望其指定的参与者或相关人员能安全地接收结果，而不会让分析结果也被泄露。


最近，有许多关于在不可信服务器上进行隐私保护的众包统计聚合和分析的工作，一个重要的技术路线是采用密态计算技术，保障统计分析过程的加密安全性，例如~\cite{miao2017lightweight, zhang2022enabling, yan2023fog}。一种常见的方法是使用同态加密，在不受信任的云服务器上对用户的加密数据进行安全聚合与分析。最近的研究~\cite{lu2017using,lee2023heaan}利用基于环上容错学习问题~\cite{lyubashevsky2010ideal}的全同态加密方案或者部分同态加密方案来支持包含加法和乘法运算的聚合分析任务。然而，由于同态加密的局限性，许多其他操作可能更具挑战性。对于依赖于比较或排序关系的统计函数，例如最大/最小值、百分位数、列联表等，现有方案需要复制非常多的密文，使得密文数量迅速增加~\cite{lu2017using}；或者需要对密文进行深度很高的乘法运算，使得计算成本非常高~\cite{lee2023heaan}。安全多方计算提供了一种密态计算的方法，它依赖于多个非共谋的服务器进行计算，可以更容易地实现多样化的计算功能。目前已有多种基于安全多方计算技术的安全统计分析工具~\cite{bogdanov2014privacy, bogdanov2018rmind}。Rmind~\cite{bogdanov2018rmind}使用秘密共享进行在线的交互计算，可以实现包括最大/最小值、分位数、直方图、简单的统计度量、离群值检测、t检验、卡方检验、有符号秩检验与秩和检验以及线性回归等多种统计分析功能。然而，基于安全多方计算的方案的通信或交互成本通常高于基于同态加密的方案。此外，限制基于MPC的安全统计分析工具实际应用的还包括很强的安全假设，需要依赖于多个不共谋的服务器执行交互计算。

众包场景仍然迫切需要一个隐私保护框架，以便安全地聚合多源数据，并能够让众包请求者在不受信任的云服务器上进行统计分析计算，在具有高效率和可扩展性的同时，提供强大的隐私保证，不向云服务器和众包请求者暴露用户的数据隐私。然而，许多重要问题仍有待解决。

首先，在执行众包统计分析任务时，通常需要安全地收集和聚合众包数据，并结合应用多种统计分析功能。一个实用的隐私保护统计分析框架对于大多数统计分析功能来说都应该是高效的。然而单靠现有的基于同态加密或安全多方计算的解决方案总是难以实现这一目标，因为只支持单一密态计算技术的框架在功能或效率上有局限性。受近期加密神经网络推理研究~\cite{juvekar2018gazelle,rathee2020cryptflow2,huang2022cheetah}的启发，本研究通过在基于同态加密的协议和安全两方计算之间搭建一座桥梁来打破这种限制。方案采用服务器-客户端架构，用户使用同态加密对数据进行加密，云端基于同态加密方案执行涉及简单线性运算（如求和聚合）的安全分析。对于包含非线性操作的函数，它们可以转换到安全两方计算协议上来执行，由众包请求者的客户端和云端服务器交互地执行计算。这样，可以使用更友好的安全计算技术实现特定的统计分析功能，同时可以在框架中实现多种类型的安全统计功能的组合，满足复杂多样的统计分析的功能和效率需求。

其次，在处理众包收集的大量数据时，框架必须具有良好的可扩展性。结合特定安全计算技术设计高效的统计分析算法至关重要。对于许多统计功能来说，收集和处理数值型的数据是简单易行的，例如 Rmind~\cite{bogdanov2018rmind} 中的许多算法设计。 然而，对于需要排序和频数信息的一些统计函数，如分位数、为卡方检验构建列联表、曼-惠特尼\textit{U}检验等，使用数值型数据设计的协议必须进行安全排序，而且通常对于数据点总量的扩展性较差，带来无法忍受的开销。本方案的主要想法是在面向众包的框架中引入直方图，将其与数值型数据一起作为主要数据类型。数据可以在用户侧编码，直方图在云端通过执行安全聚合获得。在直方图上执行统计函数的开销对数据点数量的变化不敏感，因此具有更好的可扩展性。在安全计算技术层面，由于隐私保护算法在并行执行时效率明显更高，本研究选择了 BFV 同态加密方案~\cite{fan2012somewhat} 和基于不经意传输的最先进的安全两方计算协议~\cite{rathee2020cryptflow2,rathee2021sirnn}，它们在向量化地处理大量数据时表现出色。因此，这样的协议更适合处理直方图向量。与基于另一种常见的安全两方计算技术——混淆电路的协议相比，基于不经意传输的协议通常需要更少的计算和通信开销。利用这些技术，本方案为使用直方图向量进行统计分析提供了新的高效协议。

另一个关键问题涉及密钥的安全性，这是在众包场景中结合使用同态加密和安全两方计算协议时产生的。在现有设计~\cite{juvekar2018gazelle,rathee2020cryptflow2}中，将同态加密密文转换为安全两方计算的秘密共享份额往往需要使用私钥进行解密。这种方法适用于加密神经网络推理，其中数据提供者和服务请求者是同一方，因此它们可以拥有私钥。然而在众包场景中，需要从用户那里收集大量的数据，依赖单一私钥可能会带来安全风险。例如，当考虑拥有私钥的一方对用户数据的密文进行窃听攻击时，用户的隐私很容易被泄露。这使得当用户和云端不存在一个可靠的安全消息通道时，难以抵御一个被动攻击的敌手。因此，有必要采用更安全的密钥分离设计，将用于加密用户数据的密钥对与用于请求者解密最终结果的密钥对分开。

为了解决上述问题，本研究为众包应用提出了一个新的隐私保护统计分析框架的设计方案。本方案的主要贡献可总结如下：

\begin{enumerate}
    \item 本方案为众包服务提出了一种加密安全的隐私保护统计分析框架。它能够将基于同态加密和安全两方计算的统计分析协议结合起来，克服了只支持单一安全计算技术在功能和效率上的限制。
    \item 本方案引入了安全的直方图聚合协议，并提出了使用直方图进行隐私保护统计分析的新算法设计，对于密态数据更加友好。得益于同态加密方案和安全两方计算协议所支持的向量化操作，本方案提出了对数据规模具有出色的可扩展性的高效协议。
    \item 认识到众包场景中与单个密钥相关的潜在安全问题，本方案为框架提出了密钥分离设计，并通过引入 MBFV 方案实现了该设计。这确保了除了请求者可以解密并获得分析结果之外，任何一方都不能独立解密其他任何密文，从而保障了强大的加密安全性。
    \item 本研究评估了方案中提出的框架的性能，并将本方案使用直方图的协议与其他安全统计分析工作中提出的协议进行了比较。结果明确地验证了本方案提出的框架和协议的效率和可扩展性。
\end{enumerate}

\section{系统模型}



\subsection{系统架构}


在本方案的系统模型中，主要采用客户端-服务器架构，由众包服务提供者的服务器和众包任务请求者的客户端交互计算，实现安全的统计分析，而不依赖于多个不共谋的众包服务器。本方案的系统模型如\Cref{fig:PSAC_system_model}所示，其中各方的具体角色如下。

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/PSAC_system_model.pdf}
    \caption{面向众包数据的隐私保护统计分析方案的系统模型}\label{fig:PSAC_system_model}
\end{figure}


\begin{itemize}
    \item \textbf{聚合服务器 （Aggregation Server，AS）:} AS是众包服务提供商部署的独立云服务器，用于收集和汇总聚合大量用户的数据。此外，AS 还与 RC 交互，利用聚合的数据执行各种统计分析计算。
    \item \textbf{请求客户端 （Request Client，RC）:} 请求者选择并使用 RC 与 AS 交互，以进行安全计算。RC 可以是请求者私有的，也可以托管在第三方云平台上。
    \item \textbf{请求者：} 请求者是需要最终统计分析结果的统计分析师，需要获得最终的统计分析结果。
    \item \textbf{用户：} 用户在参与众包任务时负责收集数据并加密上传到 AS。本方案用 $\mathbf{U}=\{u_1,u_2,\ldots,u_K\}$ 表示用户集合。此外，在本方案中还用 $P$ 表示所有用户上传的数据点数量。
\end{itemize}


\subsection{威胁模型}\label{subsec:PSAC_threat_model}

在本方案的威胁模型中，同时考虑了外部威胁和内部威胁。外部威胁的敌手会发起被动攻击，即试图窃听通信网络和捕获实体间传输的信息，以推断用户的隐私数据和请求者想要获取的统计分析结果。至于内部威胁，本方案考虑聚合服务器、请求客户端、请求者和用户的以下威胁模型：

\begin{itemize}
\item \textbf{聚合服务器，请求客户端和请求者：} 本方案假设这些实体是半诚实的。也即他们会诚实地遵守协议，却对用户的隐私数据充满好奇。对于共谋模型，本方案假设 AS 或 RC 最多可以与 $K-1$ 个用户共谋，获取这些用户的密钥和数据。但是，AS 和 RC 之间以及 AS 和请求者之间不能共谋。此外，本方案假设请求者可以获取 RC 所知道的所有信息，包括 RC 的数据和密钥，但 RC 无法获取请求者的所有数据和密钥。
\item \textbf{用户：} 本方案假设用户也是诚实但好奇的，他们会诚实遵守协议，但也对其他用户的隐私数据感到好奇，并参与和请求客户端、请求者或聚合服务器的共谋行为。
\end{itemize}

这种半诚实的威胁模型在众包系统中很常见~\cite{yan2023fog,zhang2023privacyeafl,zhao2023crowdfa,zheng2023efficient}。在安全的两方计算中，一个基本假设是两个参与方之间不存在共谋。出于实际部署的考虑，本方案假设请求者可以部署 RC。因此，请求者可以访问 RC 所知道的所有信息，因为请求者可以控制 RC。但是，请求者不希望 RC 所在的云服务提供商知道其私钥和分析结果。

\subsection{设计目标}

这个工作目的在于面向众包的大量数据，提供一种不依赖于多个不共谋服务器的统计分析框架，以实现常用的统计分析功能。框架应当包含两部分，一方面是对用户数据的编码、加密及安全聚合，以安全地采集众包的数据，并获得求和、直方图等基本的聚合统计信息；另一方面需要在收集的密态数据的基础上实现多样化的统计分析功能。最终，统计分析的结果以密文的形式安全地递交给众包请求者，以获得统计分析的结果报告。本方案对于框架的设计目标如下：


\begin{itemize}
    \item \textbf{加密安全性：}本方案侧重于提供加密安全性。形式化地来讲，在计算函数 
    \begin{equation}
        (\llbracket{y_{1}}\rrbracket,\ldots,\llbracket{y_{n}}\rrbracket)\leftarrow f(\llbracket{x_{1}}\rrbracket,\ldots,\llbracket{x_{m}}\rrbracket)
    \end{equation}
    时，除了输出给请求者的结果之外，服务器不能访问任何隐私输入 $x_{i}$（其中 $i\in\set{1,\dots,m}$）、输出 $y_{j}$（其中 $j\in\set{1,\dots,n}$）以及计算 $f$ 时产生的中间值。此外，根据Rmind~\cite{bogdanov2018rmind}，具有加密安全性的协议也是满足数据源隐私的，即计算$f(x_{1},\ldots,x_{m})$的算法的所有输出和所有中间值都不依赖于输入的顺序。
    
    \item \textbf{密钥分离设计：}框架应采用密钥分离设计，以避免单私钥设计带来的安全风险。一方面，没有一个私钥可以用来解密用户的加密数据和中间结果。另一方面，最终结果只能使用请求者持有的密钥独立解密，确保只有请求者而非请求客户端才能获得最终结果。这就保障了当任何一方获取结果之外的任何密文时，也无法独立解密。

    \item \textbf{功能的可组合性：}统计分析任务可能包含多个统计函数的顺序执行，为了不对中间结果进行解密，这些协议需要具有可组合性。一方面，当一个协议的输出与另一个协议的输入格式相同时，两个协议可以依次组合。另一方面，该框架可以与使用MPC原语设计的其他协议兼容和组合，以扩展更多的功能。

    \item \textbf{高效性和可扩展性：}本方案中提出的基于直方图的协议在设计时需要降低执行计算和通信开销。特别是，它们需要对用户的数据量具有良好的可扩展性，而如果这些统计分析功能如果使用数值型数据实现将是极其昂贵的。
\end{itemize}



此外，本方案不对 $P$ 保密，也即众包统计分析研究计划中所需的数据点数量是系统所公开的。本方案还将数据点的取值空间视为背景信息，以帮助选择合适的参数，它并不是所收集数据点的实际的范围。

输出隐私是指分析的输出不会泄露隐私输入。输出隐私不可能是绝对的，因为统计分析任务所需的有用信息必须从输入中获取。差分隐私有助于提供输出隐私，但可能会降低分析的准确性。与 Rmind 一样，本方案的目的是让请求者能够获取准确的统计分析结果，因此输出安全保护必须是为框架扩展出的一个独立的层。在保证框架的加密安全性的同时，定义一种适用于统计分析框架的差分隐私机制，这是一个独立于本方案之外的研究方向，也可能是未来的目标。


\section{方案设计}

\subsection{方案概述}

在这个方案中，使用定点数来表示统计分析计算中的小数，采用多方同态加密方案MBFV~\cite{mouchet2021multiparty}和CrypTFlow2~\cite{rathee2020cryptflow2} 所提供的安全两方计算的原语组合设计本方案的框架。其中MBFV方案是同态加密方案BFV的拓展，在BFV方案提供的加密原语的基础上，放弃了单个私钥$\sk$，使用集体加密密钥$\cpk$加密消息，各方持有$\cpk$对应的理想的私钥$\sk$的秘密共享份额，提供分布式的解密、公钥转换、同态密文和加法秘密共享之间互相转换的功能。后者提供了\Cref{subsec:vectorized_2pc}中提到的基于不经意传输的多种基本的数学函数原语，能够实现秘密共享比较大小、乘法、定点数截断、除法、多路选择器、布尔秘密共享转换算数秘密共享等本方案设计安全计算协议所需要的功能。

众包统计分析的整个过程简述如下。
\begin{enumerate}
    \item[1）] 请求者向众包服务提供者发起任务。
    \item[2）] 服务提供者、请求者和用户商定统计分析研究计划和要收集的数据格式，并初始化参数。
    \item[3）] 用户加密数据并上传至 AS。
    \item[4）] 请求者根据计划发送允许的查询，并使用 RC 与 AS 使用收集的数据进行交互式计算。
    \item[5）] 请求者得到最终结果。
\end{enumerate}

步骤1）和2）是众包统计分析任务的准备过程，而这项工作的重点是为步骤3）至5）提供一个具有加密安全性的隐私保护框架。本方案所提出的框架的主要组成部分如\Cref{fig:PSAC_components}所示。

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/PSAC_components.pdf}
    \caption{面向众包数据的隐私保护统计分析框架的主要组成部分}\label{fig:PSAC_components}
\end{figure}


本方案从\textbf{系统初始化阶段}开始，生成加密和使用用户的数据计算所需的密钥 $(\cpk, \sk_0, \sk_1)$，以及请求者的密钥对$(\sk', \pk')$。之后，在\textbf{安全聚合阶段}中，聚合服务器安全地收集使用$\cpk$加密的用户数据，并计算用户数据向量的统计求和。特别是，本方案引入了\textbf{指标编码}，并实现了\textbf{安全的直方图聚合}，作为新的统计分析协议所需的数据类型。

在\textbf{安全统计分析阶段}，AS和RC使用加密数据和直方图作为输入，通过组合和交互式执行统计分析协议来完成分析任务。本方案介绍了两种数据类型：数值型数据和直方图向量，并重点使用直方图设计统计协议。在本方案中，这些协议是使用常用的同态加密方案和抽象的MPC原语设计的，使框架与类似原语设计的协议兼容。此外，基于MBFV方案，本方案提供了同态密文和秘密共享之间的转换协议，将基于同态加密和基于安全两方计算的协议结合起来。这些协议不依赖于单个密钥来解密中间值。最后，在安全输出阶段，再次使用MBFV方案，本方案将使用$\cpk$加密的结果的密文转换为使用请求者的公钥$\pk'$加密的密文，确保只有请求者可以访问最终结果。由于密钥分离的设计，用于加密用户数据的密钥对和用于解密最终结果的密钥对是分开的，任何一方都不能独立解密用户数据的密文或中间值。

\subsection{系统初始化阶段}

首先，执行以下步骤以提供通用参数并为后续协议生成密钥。

\begin{enumerate}
    \item \textbf{同态加密初始化：}给定一个安全参数$\lambda$，AS执行初始化函数$\bfvSetup(1^{\lambda})$，并为BFV和MBFV方案生成公共参数$pp$。
    \item \textbf{AS和RC的密钥生成：}在本方案中，将AS视为$P_0$，将RC视为$P_1$，它们执行函数$\mbfvSecKeyGen(pp)$以获得自己的$\sk_i$，其中$i=0,1$。私钥$\sk_0$和$\sk_1$是使用$\mbfvEtoS$和$\mbfvStoE$进行BFV密文和秘密共享之间的相互转换所必需的。
    \item \textbf{集体加密密钥生成：}AS和RC执行$\mbfvEncKeyGen(\sk_0,\sk_1)$以生成公钥$\cpk$，然后将其提供给用户进行数据加密。
    \item \textbf{安全输出密钥生成：}请求者通过依次调用$\bfvSecKeyGen(pp)$和$\bfvPubKeyGen(\sk')$来生成请求者的私钥$\sk'$和公钥$\pk'$。然后，$\pk'$被发送到AS和RC，用于进行密钥转换，以输出最终结果的密文$\ct'$，该密文只能使用$\sk'$解密。
\end{enumerate}


\subsection{安全聚合阶段}\label{subsec:PSAC_secure_agg}

首先，本小节介绍基本的\textbf{安全向量聚合协议}。该协议一方面能够从用户那里收集多个加密值，另一方面又可以对这些值进行求和。然后，本小节介绍基于该基本协议的\textbf{安全直方图聚合协议}。它允许本方案在不泄露用户数据的情况下获得直方图向量，它是框架中需要的除数值型数据外另一种重要数据类型。

\paragraph{安全向量聚合协议。}
对于数据点具有多维值的众包任务，用户可以在单个消息中打包和加密多个值。对于用户$u_{k}$，可以将其数据的值视为$L$维向量$\mathbf{m}_{k}=[m_{k,1}, m_{k,2}, \ldots, m_{k,L}]$。

\begin{enumerate}
    \item \textbf{数据报告：}用户$u_{k}$打包向量$\mathbf{m}_{k}$为多项式$\hat{m}_{k} \in R_t$，并使用BFV方案使用集体加密密钥$\cpk$加密数据。具体来说，用户$u_{k}$计算 $\ct_{k}=\bfvEnc(\cpk,\hat{m}_k)$，并将$\ct_{k}$发送给AS。向量中元素的顺序和打包方法根据计划预先商定。
    \item \textbf{数据聚合：} 当AS收到用户$u_{k}$报告的$\ct_{k}$时，$\ct_{k}$被累加以计算
    \begin{equation}
        {\ct_{\textnormal{Sum}}} = \ct_1\oplus\ldots\oplus\ct_K
    \end{equation}
\end{enumerate}

通过聚合用户的密文，AS 得到 ${\ct_{\textnormal{Sum}}}$，即 $\sum^K_{k=1}{\hat{m}_{k}}$ 的密文。如果 $\hat{m}_{k}$ 是使用 SIMD 打包的，那么 $\sum^K_{k=1}{\mathbf{m}_{k}}=(M_1,M_2,\ldots,M_L)$  可以通过解包 $\sum^K_{k=1}{\hat{m}_{k}}$ 轻松获得，其中 $M_l=\sum^K_{k=1}{m_{k,l}}$。
另一种可选的打包方法是直接设置 $\hat{m}_{k}$ 的系数。由于 $\hat{m}_{k}$ 是一个模$X^n+1$的多项式，其系数模 $\mathbb{Z}_t$。因此它有 $n$ 项。如果所有用户都按相同顺序将数据向量的元素填入多项式的系数中，并将其余项的系数设为 0，那么多项式的求和就等同于向量的求和。例如，每个用户 $u_{k}$ 设置其 $\hat{m}_{k}=\sum_{l=1}^{L}{m_{k,l}X^{l-1}}$，因此 $\sum^K_{k=1}{\hat{m}_{k}}=\sum_{l=1}^{L}{M_{l}X^{l-1}}$ 。有了这种非 SIMD 打包，就可以直接操作编码值的位置，例如在\Cref{subsec:PSAC_mann_whitney_u_test}中给出的基于同态加密的曼-惠特尼\textit{U}检验协议。

\paragraph{安全直方图聚合协议。}
安全地获取直方图是本方案的重要一步。通过使用\textbf{指标编码}，用户可以将数值型数据编码成一个向量。通过执行安全的向量聚合，就可以得到\textbf{直方图向量}。


\textbf{直方图向量：} 考虑一个序数属性 $\mathbf{s} = \{{s}_{1},{s}_{2},\ldots,{s}_{M}\}$，其中 $M=|\mathbf{s}|$，$s_i$ 是 $\mathbf{s}$ 的第 $i$ 个状态。序数属性中的值之间有一个有意义的顺序，可以表示为 $s_i \preceq s_j$ （$i<j$ 和 $1\le i,j\le M$）。直方图向量 $\HIST = [F_{1},F_{2},\ldots,F_{M}]$是一个长度为 $M$ 的向量，其中 $F_i$ 是属于 $\mathbf{s}$ 的 $i$ 状态的\textbf{数值型数据}点的数量。



要使用序数属性来表示数据点 $x$，可以将 $x$ 的取值空间视为 $\mathbf{s}$ 中的状态，其中 $s_i$ 代表第 $i$ 个状态。本方案假设 $s_{i+1} - s_i = C$，对于 $1\le i < M$，其中 $C$ 是一个常数。在这种情况下，$C$ 定义了划分数值范围的区间宽度。在不失一般性的前提下，本方案设定 $C$ 为 1，以方便算法的描述。当$C$不等于$1$时，可以考虑对计算过程进行仿射变换，但这里不涉及这种变换的具体细节。然后，本方案在数据点上使用\textbf{指标编码}。

\textbf{指标编码：}数据点 $x$ 的指标向量可以表示为一个独热向量 $\mathbf{f}=[f_1,f_2,\ldots,f_M]$。
当 $x=s_j$ 时（$1\le j\le M$），那么 $f_j=1$，其他的 $f_i=0$ （$i\neq j$ 且 $1\le i\le M$）。例如，如果 $\mathbf{s} = \{2,3,4,5,6\}$，那么 $x=3$ 可以用 $[0,1,0,0,0]$ 表示。对所有数据点的指标向量求和就得到了直方图向量。


\textbf{用户本地聚合多个数据点：} 如果用户 $u_{k}$ 持有多个数据点，那么用户可以将这些数据点的指标向量在明文上进行本地相加，然后打包成一个消息 $\mathbf{f}_{k}$ 。例如，如果 $\mathbf{s} = \{2,3,4,5,6\}$，而工作这 $u_{k}$ 拥有数据点 $\{3,3,5\}$，那么 $\mathbf{f}_{k}=[f_{k,1},f_{k,2},\ldots,f_{k,M}]=[0,2,0,1,0]$ 。对 $k=1,\ldots,K$ 的 $\mathbf{f}_{k}$ 求和，相当于对所有 $P$ 个数据点的指标向量求和，从而得到直方图。这样，每个用户只需上传一个加密的 $\mathbf{f}_{k}$。\Cref{table:PSAC_example_histogram_agg} 展示了一个示例。

\begin{table}[ht]
    \caption{直方图聚合的例子}\label{table:PSAC_example_histogram_agg}
    \centering
    \resizebox{0.6\columnwidth}{!}{%
    \begin{tabular}{ccccccc}
    \toprule
    \multirow{2}{*}{用户} & \multirow{2}{*}{数据点} & \multicolumn{5}{c}{数据点的取值空间}\\ 
    \cmidrule{3-7}
    & & ${s}_{1}=2$ & ${s}_{2}=3$ & ${s}_{3}=4$ & ${s}_{4}=5$ & $s_{5}={6}$ \\ 
    \midrule
    $U_1$ & $\{3,3,5\}$ & 0 & 2 & 0 & 1 & 0 \\
    $U_2$ & $\{4\}$     & 0 & 0 & 1 & 0 & 0 \\
    $U_3$ & $\{3,6\}$   & 0 & 1 & 0 & 0 & 1 \\ 
    \midrule
    \multicolumn{2}{c}{$\HIST $ （直方图）} & 0 & 3 & 1 & 1 & 1 \\
    \bottomrule
    \end{tabular}%
    }
    \end{table}
    

安全直方图聚合协议可以从安全向量聚合协议直接得到。用户 $u_{k}$ 将 $\mathbf{f}_{k}$ 加密为 $\ctf{k}=\bfvEnc(\cpk,\mathbf{f}_{k})$ 并将 $\ctf{k}$ 报告给 AS。 AS执行指标向量的求和并得到：
\begin{equation}
    \CTHist = \ctf{1}\oplus\ldots\oplus\ctf{K}
\end{equation} 
其中，$\CTHist$是$\HIST = [F_{1},F_{2},\ldots,F_{M}]$的密文，并且$F_{j}=\sum^K_{k=1}{f_{k,j}}$。


\textbf{BFV密码系统的参数选择：}
一个 BFV 密文中可以打包的向量长度受参数 $n$ 的限制，它通常是密文插槽数。如果只考虑执行安全的向量聚合协议，那么选择较小的 $n$ 更高效。不过一个长的向量可以分割成多个短的向量，当为BFV方案选择用较小的 $n$时，可以打包进多个多项式中来加密。至于明文模数 $t$，对于直方图聚合，必须满足 $t > P$，这样聚合的直方图向量 $\HIST$ 中的任何元素 $F_i$ 才不会发生数值溢出。


\subsection{安全统计分析阶段}\label{subsec:PSAC_statistical_phase}

在这一阶段，AS 使用收集到的加密数据和聚合直方图向量，根据与 RC 一起制定的研究计划，安全地执行所需的统计分析协议。
这些协议需要能够按顺序组合，这意味着一个协议的输出可以用作另一个协议的输入，并且任何协议的结果都要保密，以便安全地完成复杂的任务。
下面将介绍如何设计统计函数协议。


\paragraph{数据类型选择。} 本方案的框架中可以引入将两种类型的数据作为输入的协议，即数值型数据和直方图向量，并且需要根据统计功能选择合适的数据类型。

\begin{itemize}
    \item
    \textbf{数值型数据:} 不包含排序关系的统计函数，如求和、均值、方差、协方差、矩分析，以及使用这些统计量的检验，如 Student's $t$ 检验，都可以直接使用数值型数据来实现。
    \item
    \textbf{直方图向量:} 一般来说，与数据源不相关且包含潜在排序关系的统计函数可以避免使用基于直方图的协议进行复杂的排序或排序计算，例如分位数（最大/最小值、中位数、四分位数等）和曼-惠特尼\textit{U}检验。此外，对于需要频数的统计功能，如需要列联表的卡方检验，可直接从直方图中获取，从而避免使用数值型数据进行多次相等判断以构建列联表。
\end{itemize}

\textbf{使用直方图的统计分析协议（在\Cref{sec:PSAC_statistical}中详细描述）。}
许多相关工作~\cite{bogdanov2014privacy,bogdanov2018rmind}都使用了数值型数据来设计统计分析协议。但本方案将直方图引入框架，作为一种基本地数据类型来设计统计分析协议。而这样的协议设计并非简单直接的。作为设计的另一个主要部分，本方案给出了统计分位数估计、离群值消除、为卡方检验构建列联表和曼-惠特尼\textit{U}检验的新型算法或协议。为了确保效率和可扩展性，这些协议尽可能执行并行的向量化操作，其特点是当用户的数据量增加时，成本几乎是稳定的。

\textbf{对于其他统计分析功能的支持。}
需要说明的是，本方案提出的协议关注于使用直方图来提供对数据规模具有良好扩展性的统计分析协议。因此，这些协议被设计为使用直方图作为输入，不过大多数协议仍被设计为输出受保护的数值型数据。本方案的框架可以与Rmind~\cite{bogdanov2018rmind}等其他使用数值型数据作为输入的协议相结合，从而扩展功能，实现高阶统计分析、回归分析等更复杂的统计功能。这样的协议设计是直接的，因此不在\Cref{sec:PSAC_statistical}中再给出。

\paragraph{加密方案选择。} 本方案的框架中，数据被BFV同态加密方案或者两方的秘密共享保护。本方案的安全的统计分析协议基于 BFV 方案或安全两方计算协议实现。一般来说，对于可以使用加法和乘法同态运算轻松计算的函数，本方案给出了基于同态加密的协议，例如曼-惠特尼\textit{U}检验协议。这样的协议可以由 AS 本地计算而无需交互。至于需要复杂非线性运算的协议，本方案使用以秘密共享为输入的向量化安全两方计算协议来设计它们，以并行地执行计算，从而减少迭代和交互的次数。抽象的安全多方计算原语的使用使本方案的框架能够与Rmind~\cite{bogdanov2018rmind}中定义的在秘密共享上计算的协议兼容。


\textbf{同态加密和秘密共享之间的转换。}在本方案的框架中，为了将基于同态加密的协议和基于安全两方计算的协议结合起来，需要在 BFV 密文和两方的秘密共享之间进行转换。本方案使用MBFV方案来实现。

\begin{itemize}
    \item \textbf{同态加密到安全两方计算：} 
    给定向量 $\textbf{m}$ 的 BFV 密文 $\ct_{\textbf{m}}$，AS 和 RC 交互执行 $\mbfvEtoS(\ct_{\textbf{m}},\sk_{0},\sk_{1})$，其中 $\sk_{0}$ 和 $\sk_{1}$ 分别是 AS 和 RC 持有的私钥。
    那么 AS 和 RC 可以分别获得自己的秘密共享份额 $\share{\textbf{m}}_{0}$ 和 $\share{\textbf{m}}_{1}$ 。

    \item \textbf{安全两方计算到同态加密：} 
    给定 AS 和 RC 分别持有的秘密共享份额 $\share{\textbf{m}}_{0}$ 和 $\share{\textbf{m}}_{1}$，它们交互执行 $\mbfvStoE(\share{\textbf{m}}_{0},\share{\textbf{m}}_{1},\sk_{0},\sk_{1})$，其中 AS 从 RC 处收集密文份额，并生成由集体加密密钥 $\cpk$ 加密的 BFV 密文 $\ct_{\textbf{m}}$。
\end{itemize}


\subsection{安全输出阶段}\label{subsec:PSAC_output}

执行统计分析协议后，结果 $out$ 将由使用集体加密密钥 $\cpk$ 加密的 BFV 密文 $\ct_{res}$ 保护。为了把 $out$ 安全地返回给请求者，应该把它转换成使用请求者的公钥 $\pk'$ 加密的密文 $\ct'_{res}$。由于使用无 SIMD 打包的算法会导致不需要输出的值与研究计划中需要的结果一起被加密，因此直接解密以获取整个明文可能会导致隐私泄露，例如在\Cref{subsec:PSAC_mann_whitney_u_test}中给出的基于同态加密的曼-惠特尼\textit{U}检验协议。因此，有必要让AS先通过随机掩码屏蔽 $\ct_{res}$ 中不需要的值所在的密文插槽。在\Cref{alg:PSAC_secure_output_HE} 中给出了包含密钥转换、输出向量掩码保护的安全输出协议（表示为 $\protocol{\mathsf{SecOutput}}$）。

\begin{algorithm}[htbp]
    \caption{安全输出协议 $\protocol{\mathsf{SecOutput}}$}\label{alg:PSAC_secure_output_HE}
    \Input{$\ct_{res}\in R_q$，结果向量$\mathbf{res}$中需要保留的向量下标集合 $\mathbf{D}$ 和请求者的公钥 $\pk'$；}
    \Output{一个使用请求者的公钥 $\pk'$ 加密的密文 $\ct'_{res}$。请求者解密后可以获得 $\mathbf{res}[i]$，其中 $i\in \mathbf{D}$；}
    AS 随机生成 $\mathbf{mask}=[a_{1}, a_{2}, \ldots,a_{L}]$，
    如果 $i\notin \mathbf{D}$， $a_i$ 从 $\mathbb{Z}_t$中独立且均匀地随机选取，否则 $a_i=0$；\\
    AS 计算 $\ct_{mask}=\ct_{res}\oplus \Pack(\mathbf{mask})$ 并发送给 RC；\\
    AS 和 RC 一同交互执行 $\ct'_{res}=\mbfvPubKeySwitch(\ct_{mask},\pk',\sk_0,\sk_1)$，其中 AS 发送自己关于 $\ct'_{res}$的密文份额给 RC，RC 生成 $\ct'_{res}$；\\
    最后请求者从RC处接收 $\ct'_{res}$ 并解密获得 $\mathbf{res}=\Unpack(\bfvDec(\sk',\ct'_{res}))$。其中 $\mathbf{res}[i], i\in \mathbf{D}$ 是输出的结果，其余项都被随机掩码保护；
\end{algorithm}


\section{使用直方图的隐私保护统计分析协议}\label{sec:PSAC_statistical}


这一节主要给出本方案中新的使用直方图的安全统计分析协议，包括在\Cref{subsec:PSAC_statistical_phase}中提到的分位数估计（可以被扩展为最大值/最小值统计）、离群值消除、为卡方检验构建列联表和曼-惠特尼\textit{U}检验协议。

\subsection{安全的分位数估计协议}\label{subsec:PSAC_quantile_estimation}


分位数估计功能可用于计算任何分位数值。将 $p$ 分位数表示为 ${Q}_{p}$，这样一些常用的分位数，如下四分位数、中位数和上四分位数，可以分别表示为 ${Q}_{1/4}$、${Q}_{1/2}$ 和 ${Q}_{3/4}$。令 $\mathbf{a}$ 为按升序排序的所有数据的向量，$\mathbf{a}$ 的 $p$ 分位数${Q}_{p}$ 可以计算为
\begin{equation}
    \mathbf{Q}(p,\mathbf{a})=(1-\gamma)\cdot a_{j}+\gamma\cdot a_{j+1}
\end{equation}
其中，$j=\lfloor (P'-1)p \rfloor +1$，$a_j$ 和 $a_{j+1}$ 分别是第 $j$ 个和第 $j+1$ 个最小数据点，$P'$ 是 $\share{\mathbf{a}}$ 中的数据点数量，$\gamma=(P'-1)p-\lfloor(P'-1)p\rfloor$。
由于本方案可以使用\Cref{subsec:PSAC_outlier_elimination} 中的离群值消除协议 $\protocol{\Outlier}$ 来过滤并消除直方图中的离群值，因此 $P'$ 可以不等于 $P$。如果研究计划不允许 $P'$ 暴露，就需要保护 $P'$。\Cref{alg:quantile_estimation} 是使用直方图的安全的分位数估计协议，它输出$p$分位数 $Q_p$的值，其中$a_j$和$a_{j+1}$可以使用直方图向量计算，而无需对数值型数据进行排序。本方案的协议使用 $\mathbb{Z}_{2^l}$ 上的秘密共享计算，因此协议使用分数 $p'/{2^{l'}}$ 来（近似地）表示 $p$，这会使得协议设计更加方便。协议的计算结果 $Q_p$ 是缩放大小为 $2^{l'}$ 的定点数。

\begin{algorithm}[ht]
    \caption{安全的分位数估计协议 $\protocol{\Quantile}$}\label{alg:quantile_estimation}
    \Input{$\share{\HIST}^{l}=[\share{F_{1}}^{l},\share{F_{2}}^{l},\ldots,\share{F_{M}}^{l}], p=p'/2^{l'}$；}
    \Output{分位数 $\share{Q_{p}}^{l,l'}$，缩放大小为$2^{l'}$；}

    $\share{P'}^{l}=\sum^{M-1}_{i=1}{\share{F_i}^{l}}$；\label{alg_line:K_prime}\\
    \uIf{$P'=P$}{
    AS 发送 $\share{P'}^{l}_0$ 给 RC；\\
    RC 重建 $P'$ 并计算 $j=\lfloor (K'-1)p \rfloor +1$，然后将 $\share{j}^{l-l'}$ 秘密共享给 AS；
}
    \Else{
        $\share{j}^{l-l'}=\Trunc_{l,l'}((\share{P'}^{l}-\share{1}^{l})\cdot p')+\share{1}^{l-l'}$；
    }
    $\share{\gamma'}^{l,l'} = (\share{P'}^{l}-\share{1}^{l}){p'}- (\share{j}^{l-l'}-\share{1}^{l-l'}) \ll {l'}$；\label{alg_line:gamma_prime}\\ 
    AS 和 RC 初始化 $\share{\mathbf{V}}^{l}=[\share{V_1}^{l},\share{V_2}^{l},\ldots,\share{V_{M}}^{l}]$，其中 $\share{V_1}^{l}=\share{F_1}^{l}$；\\\label{alg_line:acc_hist1}
    \For{$i=2$ to $M$}{
        $\share{V_i}^{l}=\share{V_{i-1}}^{l}+\share{F_{i}}^{l}$；\\
    }\label{alg_line:acc_hist2}
    $\share{\mathbf{L}}^{B},\share{\mathbf{E}}^{B}=\LessOrEqual_{l-l'}(\share{\mathbf{V}}^{l}\mod 2^{l-l'},\share{j}^{l-l'})$；\label{alg_line:compare_V_j}\\ 
    $\share{\mathbf{L}|\mathbf{E}}^{l}=\BtoA_{l}(\share{\mathbf{L}|\mathbf{E}}^{B})$；\label{alg_line:BtoA}\\ 
    $\share{\text{Count}_{L}}^{l}=\sum^{M-1}_{i=1}{\share{L_{i}}}^{l}, \share{\text{Count}_{E}}^{l}=\sum^{M-1}_{i=1}{\share{E_{i}}}^{l}$；\\
    $\share{W}^{l,l'}=\Multiply_{l}(\share{\gamma'}^{l,l'},\share{\text{Count}_{E}}^{l})$；\label{alg_line:W}\\ 
    $\share{Q_p}^{l,l'}=(\share{{s}_{1}}^{l}+\share{\text{Count}_{L}}^{l})\cdot 2^{l'}+\share{W}^{l,l'}$；\label{alg_line:Qp}
\end{algorithm}


\begin{correctness}
    \Cref{alg_line:acc_hist1}到\cref{alg_line:acc_hist2}计算累积直方图 $\textbf{V}$，其中 $V_i$ 是不大于 $s_{i}$ 的数据点的数量。 在 \cref{alg_line:compare_V_j}中，协议 $\LessOrEqual$ 将 $\mathbf{V}$ 中的每个元素 $V_i$ 与 $j$ 进行比较，并输出两个向量 $\mathbf{L}$ 和 $\mathbf{E}$ 。
    如果 $V_i < j$，相应的 $L_{i}$ 在 $\mathbf{L}$ 中为 1，否则 $L_{i}$ 为 0；如果 $V_i = j$，相应的 $E_{i}$ 在 $\mathbf{E}$ 中为 1，否则 $E_{i}$ 为 0。
    \Cref{alg_line:BtoA}中符号``$|$'' 表示连接两个向量，以并行地执行 $\BtoA$ 。
    因此，$\text{Count}_{L}$ 和$(\text{Count}_{L}+\text{Count}_{E})$ 分别是按升序排列的小于第 $j$ 个数据和第 $j+1$ 个数据的数据个数，$a_j=s_1+\text{Count}_{L}$，$a_{j+1}=s_1+\text{Count}_{L}+\text{Count}_{E}$。
    因此，正如\cref{alg_line:Qp}，
\begin{equation}
    \begin{aligned}
    Q_p=&(1-\gamma)({s}_{1}+\text{Count}_{L})+\gamma({s}_{1}+\text{Count}_{L}+\text{Count}_{E})\\
       =&{s}_{1} + (\text{Count}_{L}+\gamma\text{Count}_{E})
    \end{aligned}
\end{equation}
    为了确保不发生溢出，必须满足$l\ge \lceil\log_{2}(\max(P,s_{M})) \rceil +{l'}$，其中 $s_{M}$ 是取值空间 $\mathbf{s}$ 中的最大值。
\end{correctness}
    
使用直方图的分位数估计协议的设计方法也可用于构建最大值/最小值协议。方法是直接在直方图上找到第一个或最后一个不为 0 的位置 $j$。在 $\mathbf{s} = \{{s}_{1},{s}_{2},\ldots,{s}_{M}\}$ 中，与该位置相对应的状态 $s_j$ 将是最小值或最大值。例如，可以通过设置 $p=0,\gamma=0$ 和 $l'=0$，并将\Cref{alg_line:compare_V_j}中的 $\mathbf{V}$ 和 $j$ 的比较改为判断 $\Equal(\mathbf{V},0)$ （即 $\Less(\mathbf{V},1)$）来计算最小值，因为直方图中不会有小于零的频数。这样就可以省略\Cref{alg_line:K_prime}到\Cref{alg_line:gamma_prime}，以及\Cref{alg_line:W}的计算（因为 $W=0$），同时改变秘密共享位宽的成本也节省了。由于篇幅有限，这里省略了最大值/最小值的具体协议。

\subsection{安全的离群值消除协议}\label{subsec:PSAC_outlier_elimination}

四分位距 (IQR) 是判断数据离群值的常用方法。在从用户处收集的所有数据中，数据点 $x$ 将被视为离群值，如果满足
\begin{equation}
    x>(Q_{3/4}+k\cdot\text{IQR}) \vee x<(Q_{1/4}-k\cdot\text{IQR})
\end{equation}
其中，$\text{IQR}= Q_{3/4}-Q_{1/4}$ 且 $k\ge 0$，可用来表示离群值的异常程度。
结合使用\Cref{alg:quantile_estimation}中的分位数估计协议，可以安全地计算上四分位数 $Q_{3/4}$ 和下四分位数 $Q_{1/4}$。而\Cref{alg:outlier_elimination}是消除离群值的协议，它直接在直方图向量 $\share{\HIST}$ 中设置离群值的频数为0，以方便利用直方图向量进行其他统计计算。由于该协议不会过滤掉特定的数据点，因此数据源隐私也得到了保护。根据\Cref{alg:quantile_estimation} 中的分位数估计协议，$Q_{3/4}$ 和 $Q_{1/4}$ 是按 $2^{l'}$ 的比例缩放的。

\begin{algorithm}[ht]
    \caption{安全的离群值消除协议 $\protocol{\Outlier}$}\label{alg:outlier_elimination}
    \Input{$\share{\HIST}^{l}$，$\share{Q_{3/4}}^{l,l'}$，$\share{Q_{1/4}}^{l,l'}$，$k=k''/2^{l''}$；}
    \Output{消除了离群值的直方图向量$\share{\HIST^{*}}^{l}$，其中离群值的频数设置为0；}
    $\share{I}^{l,l'+l''}=(\share{Q_{3/4}}^{l,l'}-\share{Q_{1/4}}^{l,l'})\cdot k''$；\\
    $\share{x_H}^{l,l'+l''}=(\share{Q_{3/4}}^{l,l'}-\share{{s}_{1}}^{l}\cdot 2^{l'})\cdot 2^{l''}+\share{I}^{l,l'+l''}$，
    $\share{x_L}^{l,l'+l''}=(\share{Q_{1/4}}^{l,l'}-\share{{s}_{1}}^{l}\cdot 2^{l'})\cdot 2^{l''}-\share{I}^{l,l'+l''}$；\\
    ${\share{\mathbf{x}_H}^{l,l'+l''}=[\underbrace{\share{x_H}^{l,l'+l''}, \ldots,\share{x_H}^{l,l'+l''}}_{M}]}$，
    ${\share{\mathbf{x}_L}^{l,l'+l''}=[\underbrace{\share{x_L}^{l,l'+l''}, \ldots,\share{x_L}^{l,l'+l''}}_{M}]}$；\\
    $\share{\mathbf{s}}^{l,l'+l''}=[\share{0}^{l}, \share{{s}_{2}-{s}_{1}}^{l}, \ldots,\share{s_{M}-{s}_{1}}^{l}]\cdot 2^{l'+l''}$；\\
    $\shareB{\mathbf{L}_{H}|\mathbf{L}_{L}}=\Less_{l}(\share{\mathbf{x}_{H}|\mathbf{s}}^{l,l'+l''},\share{\mathbf{s}|\mathbf{x}_{L}}^{l,l'+l''})$；\label{alg_line:oe_equal}\\
    $\shareB{\mathbf{L}}=\XOR(\shareB{\mathbf{L}_{H}},\shareB{\mathbf{L}_{L}})$；\label{alg_line:oe_xor}\\
    $\share{\HIST^{*}}^{l}=\Mux_{l}(\shareB{\mathbf{L}},\share{\HIST}^{l})$；\label{alg_line:oe_mux}
\end{algorithm}

\begin{correctness}
由于 $x_H$ 和 $x_L$ 是受保护的，所以离群值边界的位置是通过在\Cref{alg_line:oe_equal}进行比较来确定的。然后在\Cref{alg_line:oe_xor}得到确定离群值的布尔向量 $\mathbf{v}$，其中 $v_{i}=1$ 表示对应的状态 $s_i$ 是离群值，否则 $v_i=0$。因此，在\Cref{alg_line:oe_mux}使用多路选择器 $\Mux$ 将直方图向量 $\HIST$ 中的离群值对应状态的频数设置为 0。为了确保不发生溢出，对于协议$\protocol{\Outlier}$，$l\ge\lceil\log_{2}(\max(P,M)\cdot\max(k'',2^{l''}))\rceil+l'+1$ 应当满足；以及对于协议 $\protocol{\Quantile}$，$l\ge\lceil\log_{2}(s_{M})\rceil+l'$ 应该满足。
\end{correctness}

\subsection{为卡方检验构建列联表的安全协议}\label{subsec:chi2_test}

对于离散变量的值，卡方检验 （Chi-Squared Test 或 $\chi^2$ Test）的计算过程为
\begin{equation}
    \label{equ:chi2}
    \chi^2=\sum^{M_{2}}_{j=1}{\sum^{M_{1}}_{i=1}{\frac{{(F_{i,j}-E_{i,j})}^{2}}{E_{i,j}}}}
\end{equation}
其中，$F_{i,j}$ 是各个分类中观察值的计数，$E_{i,j}$ 是第 $j$ 个选项和第 $i$ 组的计数的期望。然后可以用列联表来表示这些计数，如\Cref{table:chi2_test}所示。

\begin{table}[htbp]
\caption{卡方检验的列联表}\label{table:chi2_test}
\centering
\resizebox{0.5\columnwidth}{!}{
\begin{tabular}{ccccc}
    \toprule
                & 选项 $1$  & $\ldots$ & 选项 $M_{2}$ & 总计    \\
    \midrule
    分组 $1$  & $F_{1,1}$ & $\ldots$ & $F_{1,M_{2}}$  & $R_{1}$  \\
    $\ldots$ & $\ldots$  & $\ldots$ & $\ldots$   & $\ldots$ \\
    分组 $M_{1}$  & $F_{M_{1},1}$ & $\ldots$ & $F_{M_{1},M_{2}}$  & $R_{M_{1}}$  \\
    \midrule
    总计    & $P_{1}$   & $\ldots$ & $P_{M_{2}}$    & $P$      \\
    \bottomrule
    \end{tabular}
}
\end{table}

根据\Cref{equ:chi2}，卡方检验的计算需要复杂的除法计算，使用基于安全两方计算的协议更加实用。为了提升协议执行的并行性，本方案修改了\Cref{equ:chi2} 中的计算顺序，并且使用了一个更友好的\Cref{equ:chi2_better}，其中${F_{i,j}}/{R_i}$和${F_{i,j}}/{P_j}$ 可以被同时调用来最小化交互。
\begin{equation}
    \label{equ:chi2_better}
    \chi^2=(\sum^{M_{2}}_{j=1}{\sum^{M_{1}}_{i=1}{\frac{F_{i,j}}{R_i}\cdot\frac{F_{i,j}}{P_j}}}-1)\cdot P
\end{equation}

计算\Cref{equ:chi2_better}的协议很直接，在这里省略。本方案主要关注如何实用直方图来提升构建列联表的效率。在 Rmind~\cite{bogdanov2018rmind} 中，需要对数值型数据进行大量的相等判断，以执行获取各个分类的频数。相比之下，本方案的框架允许用户直接提供编码数据，并使用直方图来构建列联表，这样更方便，也减少了计算量。

列联表可以被拉平为一个直方图向量。第 $i$ 组中第 $j$ 个选项的数据点可以表示为长度为 $M_{1}\cdot M_{2}$ 的指标向量 $\mathbf{f}$，其中 $f_{i\cdot M_{2}+j}=1$ ，这样 $F_{i,j}=F_{i\cdot M_{2}+j}$ 。因此可以使用 $\mathsf{HEto2PC}$ 协议将聚合的直方图的同态密文 $\CTHist$ 转换为秘密共享 $\share{\HIST}$ 并进行解析，得到 $i=1,\ldots,M_{1}$ 和 $j=1,\ldots,M_{2}$ 的 $\share{F_{i,j}}$ 并且 ${\share{R_{i}}=\sum^{M_{2}}_{l=1}{\share{F_{i,l}}}}$，${\share{P_{j}}=\sum^{M_{1}}_{l=1}{\share{F_{l,j}}}}$。因此，除了安全直方图聚合和执行 $\mathsf{HEto2PC}$ 协议外，构建一个列联表几乎是零成本的。

\subsection{安全的曼-惠特尼\textit{U}检验协议}\label{subsec:PSAC_mann_whitney_u_test}

假设 $X_1,\ldots,X_n$ 是来自 $X$ 的独立同分布的样本，$Y_1,\ldots,Y_m$ 是来自 $Y$ 的独立同分布的样本，且两个样本相互独立。曼-惠特尼\textit{U}检验（Mann-Whitney $U$ Test）的统计量定义为
\begin{equation}
    \label{equ:u_test}
    U=\sum_{i=1}^{n}{\sum_{j=1}^{m}{S(X_i,Y_j)}}
\end{equation}
其中，
\begin{equation}
S(X_i,Y_j)=\left\{
\begin{array}{rcl}
1,              &\text{if}& {X_i>Y_j}\\
\frac{1}{2},    &\text{if}& {X_i=Y_j}\\
0,              &\text{if}& {X_i<Y_j}
\end{array} \right.
\end{equation}

\paragraph{基于安全两方计算的曼-惠特尼\textit{U}检验协议}
曼-惠特尼\textit{U}检验的原始算法需要将从 $X$ 取样的数据与从 $Y$ 取样的数据进行比较，或将它们混合起来并排序，以确定每个数据的序数。Rmind~\cite{bogdanov2018rmind}中的协议需要多轮比较操作来在被保护的数据上实现安全排序，因此成本很高。而使用直方图的协议可以低成本地实现安全的曼-惠特尼\textit{U}检验，因为直方图包含了数据点的排序信息。假设取值空间为 $\mathbf{s} = \{{s}_{1},{s}_{2},\ldots,{s}_{M}\}$，$\HIST_{X}=[F_{X,1},\ldots,F_{X,M}]$ 和 $\HIST_{Y}=[F_{Y,1},\ldots,F_{Y,M}]$ 分别是通过对从 $X$ 取样的 $n$ 和数据点和从 $Y$ 取样的 $m$ 个数据点执行安全的直方图聚合协议得到的。\Cref{alg:U_test_SS} 是基于安全两方计算的曼-惠特尼\textit{U}检验协议。其最终结果 $U_{X}$ 和 $U_{Y}$ 是被放大了2倍的定点数。

\begin{algorithm}[ht]
    \caption{安全的曼-惠特尼\textit{U}检验协议 $\protocol{\UTest}$}\label{alg:U_test_SS}
    \Input{$\share{\HIST_{X}}^{l}, \share{\HIST_{Y}}^{l}$；}
    \Output{统计量$\share{U_{X}}^{l,1}$和$\share{U_{Y}}^{l,1}$，它们是放大2倍的定点数；}
    AS 和 RC 本地初始化存放秘密共享的向量
    $\share{\mathbf{V}_{X}}^{l}=[\share{V_{X,1}}^{l},\ldots,\share{V_{X,M-1}}^{l},0]$，$\share{\mathbf{V}_{Y}}^{l}=[\share{V_{Y,1}}^{l},\ldots,\share{V_{Y,M-1}}^{l},0]$；\\
    \For{$i = M-1,M-2,\ldots,1$}{
        $\share{V_{X,i}}^{l}=\share{F_{X,i+1}}^{l}+\share{V_{X,i+1}}^{l}$，\\
        $\share{V_{Y,i}}^{l}=\share{F_{Y,i+1}}^{l}+\share{V_{Y,i+1}}^{l}$；\\
    }\label{alg_line:V}
    $\share{\mathbf{W}_{X}}^{l,1}=\share{\mathbf{V}_{X}}^{l}\cdot 2+\share{\HIST_{X}}^{l}$，
    $\share{\mathbf{W}_{Y}}^{l,1}=\share{\mathbf{V}_{Y}}^{l}\cdot 2+\share{\HIST_{Y}}^{l}$；\label{alg_line:U1_multiply0}\\
    ${\share{\mathbf{U}_{X}|\mathbf{U}_{Y}}^{l,1}=\Multiply_{l} (\share{\HIST_{Y}|\HIST_{X}}^{l},\share{\mathbf{W}_{X}|\mathbf{W}_{Y}}^{l,1})}$；\label{alg_line:U1_multiply1}\\
    $\share{U_{X}}^{l,1}=\sum^{M}_{i=1}{\share{U_{X,i}}^{l,1}}$，
    $\share{U_{Y}}^{l,1}=\sum^{M}_{i=1}{\share{U_{Y,i}}^{l,1}}$；\label{alg_line:U1_multiply2}
\end{algorithm}

\begin{correctness}
在\Cref{alg_line:V}之后，对于向量 $\mathbf{v}_{X}$ 中的每个元素$v_{X,i}=\sum^{M}_{j=i+1}{F_{X,j}}$，以及 $\mathbf{v}_{Y}$中的每个元素 $v_{Y,i}=\sum^{M}_{j=i+1}{F_{Y,j}}$，它们分别是从$X$和$Y$的分布中采样的、小于$\mathbf{s}$中每个状态的数据点的个数。因此在\Cref{alg_line:U1_multiply0}到\Cref{alg_line:U1_multiply2}中计算了\Cref{equ:u_test} 中的曼-惠特尼\textit{U}检验统计量 $U_{X}$ 和 $U_{Y}$ 。为了确保不发生溢出，必须满足 $l\ge\lceil\log_{2}{(3P^{2}M)}\rceil$ 的条件。
\end{correctness}

\paragraph{基于同态加密的曼-惠特尼\textit{U}检验协议}

统计量 $U_{X}$ 和 $U_{Y}$ 可以由 AS 使用同态加密计算，而无需与 RC 交互。本方案使用无 SIMD 打包方法执行直方图聚合的变体，其中明文中的多项式系数被精心设置。如果用户 $u_{k}$ 的数据 $m_k={s}_{i}$ 从 $X$ 中采样，则 $u_{k}$ 令 $\hat{m}_{X,k}=x^{i-1}$ 且 $\hat{m}_{Y,k}=0$；如果 $m_k$ 从 $Y$ 中采样，则 $u_{k}$ 令 $\hat{m}_{X,k}=0$ 且 $\hat{m}_{Y,k}=x^{M-i}$。然后 $u_{k}$ 对 $\hat{m}_{X,k}$ 和 $\hat{m}_{Y,k}$ 进行加密，AS 执行聚合协议并得到 $\CTX$ 和 $\CTY$ ，它们分别是 $sum_{X}=\sum^{K}_{k=1}{\hat{m}_{X,k}}=\sum_{j=1}^{M}{F_{X,j}\cdot x^{j-1}}$ 和 $sum_{Y}=\sum^{K}_{k=1}{\hat{m}_{Y,k}}=\sum_{j=1}^{M}{F_{Y,M-j+1}\cdot x^{j-1}}$ 的密文。AS 执行如下的基于同态加密的安全的曼-惠特尼\textit{U}检验协议 $\protocol{\UTestHE}$：


\begin{enumerate}
    \item 
    $\CTWX=\CTX\otimes(2\cdot\sum^{M-2}_{i=0}{x^i}+x^{M-1})$，\\
    $\CTWY=\CTY\otimes(1+2\cdot\sum^{M-1}_{i=1}{x^i})$；
    
    \item 
    $\CTUX=\CTWX\otimes\CTY$，
    $\CTUY=\CTWY\otimes\CTX$；
\end{enumerate}

如果解密 $\CTUX$ 得到多项式 $\hat{u}_{X}$，那么 $\hat{u}_{X}$ 中的项 $U_{X}\cdot x^{2M-2}$ 的系数 $U_{X}$ 就是需要的统计量。同样，通过解密 $\CTUY$ 得到的 $\hat{u}_{Y}$ 中的项 $U_{Y}\cdot x^{M-1}$ 的系数就是统计量 $U_{Y}$。为了防止解密多项式时不需要输出的项的系数暴露出来，应该在执行 $\protocol{\mathsf{SecOutput}}$ 时屏蔽这些系数。最终结果 $U_{X}$ 和 $U_{Y}$ 也是放大了2倍的。


\begin{correctness}
根据\Cref{alg:U_test_SS}中的\cref{alg_line:U1_multiply0}，令 $\mathbf{w}_X=2\cdot\mathbf{v}_X+\HIST_X$，它被编码的多项式可以计算为
\begin{equation}
\begin{aligned}
    \hat{w}_{X}=&sum_{X}\cdot(2\sum^{M-2}_{i=0}{x^i}+x^{M-1})\\
    = & \sum_{j=1}^{M}{ (2\sum_{i=j+1}^{M}{F_{X,i}}+F_{X,j})\cdot x^{M-2+j}}+others_{1}\\
    = & \sum_{j=1}^{M}{w_{X,j}\cdot x^{M-2+j}}+others_{1}
\end{aligned}
\end{equation}
其中，$others_{1}$中的各项的幂次都小于 $M-1$。因此，具有确定系数 $U_{X}$ 的多项式 $\hat{u}_{X}$ 可以计算为
\begin{equation}
    \begin{aligned}
\hat{u}_{X} = & \hat{w}_{X}\cdot sum_{Y}\\
= & (\sum_{j=1}^{M}{F_{Y,j}w_{X,j}})\cdot x^{2M-2}+others_{2}\\
= & U_{X}\cdot x^{2M-2}+others_{2}
\end{aligned}
\end{equation}
其中，$others_{2}$中的各项的幂次都不等于 $2M-2$。类似的，令$\mathbf{w}_Y=2\cdot\mathbf{v}_Y+\HIST_Y$，它被编码的多项式可以计算为
$\hat{w}_{Y}=sum_{Y}\cdot(1+2 \sum^{M-1}_{i=1}{x^i})=\sum_{j=1}^{M}{w_{Y,j}\cdot x^{M-j}}+others_{3}$，这样$\hat{u}_{Y}= \hat{w}_{Y}\cdot sum_{X}= U_{Y}\cdot x^{M-1}+others_{4}$，其中$others_{3}$中的各项的幂次都大于$M-1$，而$others_{4}$中的各项的幂次都不等于$M-1$。

需要注意的是，为了确保不发生溢出，BFV 方案的参数必须满足 $t>3P^{2}M$。而参数 $n$ 必须满足 $n\ge 2M$，这样才能在密文中完成$\protocol{\UTestHE}$的计算，从而确保正确性。如果 $M$ 过大，则需要一个非常大且计算开销高昂的密文。在这种情况下，可以选择使用\Cref{alg:U_test_SS} 中基于安全两方计算的协议。
\end{correctness}


\section{安全性分析}\label{sec:PSAC_security}

本节将分析本方案的框架的安全性。框架的理想功能 $\mathcal{F}$ 在\Cref{fig:PSAC_functionality} 中定义，其中请求者只能解密经过安全输出协议$\protocol{\mathsf{SecOutput}}$转换的密文，并获取索引 $\mathbf{D}$ 所指示的密文插槽中的数据；而其他各方都不能独立解密任何数据。框架的安全性描述如下。

\begin{theorem}
在\Cref{subsec:PSAC_threat_model}中定义的威胁模型下，AS、RC 和共谋的用户无法获得任何信息。除了分析结果外，请求者什么也得不到。
\end{theorem}

\begin{proof}
需要证明存在有效的模拟器，使得
\begin{equation}
\begin{aligned}
    \mathsf{View}_{\text{AS}}&\approx_{c}\mathcal{S}_{\text{AS}}(\mathsf{meta})\\
    \mathsf{View}_{\text{RC}}&\approx_{c}\mathcal{S}_{\text{RC}}(\mathsf{meta})\\
    \mathsf{View}_{\text{请求者}}&\approx_{c}\mathcal{S}_{\text{请求者}}(\mathsf{meta},\mathbf{res})
\end{aligned}
\end{equation}


\begin{figure}[htbp]
    \centering
    \fbox{\parbox{\columnwidth}{
        $\mathcal{F}$ 与用户 $\{U_1,\ldots,u_{k}\}$、AS、RC 和请求者交互。\\
        \textbf{初始化：} 在接收到来自各方的\textsf{初始化}调用时，初始化具有自增索引$i$的字典$T$。$\mathcal{F}$运行给定安全参数$\lambda$的初始化过程，执行$\bfvSetup(1^{\lambda})$并向AS输出公共参数$pp$。AS 将 $pp$ 发送给其他各方。\\
        \textbf{私钥生成：} 在接收到\textsf{私钥生成}调用时，$\mathcal{F}$ 执行 $\mbfvSecKeyGen(pp)$，给AS输出 $\sk_{0}$，给 RC 输出$\sk_{1}$。\\
        \textbf{集体加密密钥生成：} 在接收到\textsf{集体加密密钥生成}调用时， AS 发送 $\sk_{0}$ 给 $\mathcal{F}$， RC 发送 $\sk_{1}$ 给 $\mathcal{F}$。 $\mathcal{F}$ 执行 $\mbfvEncKeyGen(\sk_{0},\sk_{1})$ 并输出 $\cpk$ 给各个参与方。\\
        \textbf{安全输出密钥生成：} 在接收到\textsf{安全输出密钥生成}调用时， $\mathcal{F}$ 执行 $\sk'=\bfvSecKeyGen(pp)$ 和 $\pk'=\bfvPubKeyGen(\sk')$ 并输出 $(\sk',\pk')$ 给请求者， 然后发送 $\pk'$ 给 AS 和 RC。\\
        
        \textbf{安全聚合：} 在接收到$(\textsf{安全聚合},k)$时，用户$u_{k}$ 发送 $\hat{m}_{k}$ 给 $\mathcal{F}$。$\mathcal{F}$ 令 $\ct_{k}=\bfvEnc(\cpk,\hat{m}_{k})$ 并发送 $(\textsf{安全聚合},k,\ct_{k})$ 给 $u_{k}$ 和 AS。 AS 累加 $CT_{\textnormal{Sum}}={\ct}_{1}\oplus\ldots\oplus{\ct}_{K}$。\\
    
        \textbf{基于安全两方计算的协议：} 在接收到 $(\pi,y_{0},y_{1},S_{\mathsf{in0}},S_{\mathsf{in1}})$时，其中 $\pi\in \{\Quantile,\Outlier,\UTest\}$，令 $(T[y_{0}],T[y_{1}])=\mathcal{F}^{\pi}({\{T[j]\}}_{j\in S_{\mathsf{in0}}},{\{T[k]\}}_{k\in S_{\mathsf{in1}}})$，其中 $S_{\mathsf{in0}}$ 和 $S_{\mathsf{in1}}$ 分别是 AS 和 RC 的输入的秘密共享的集合。$\mathcal{F}$ 发送 $(\pi,y_{0},S_{\mathsf{in0}})$ 给 AS，并且发送 $(\pi,y_{1},S_{\mathsf{in1}})$ 给 RC。\\
        \textbf{基于同态加密的协议：} 在接收到 $(\pi,y,S_{\mathsf{in}})$时，其中 $\pi\in\{\UTestHE\}$，令 $T[y]=\mathcal{F}^{\pi}({\{T[j]\}}_{j\in S_{\mathsf{in}}})$，其中 $S_{\mathsf{in}}$ 是输入的同态加密的密文的集合。 $\mathcal{F}$ 发送 $(\pi,y,S_{\mathsf{in}})$ 给 AS。\\
        \textbf{同态加密转换到安全两方计算：} 在接收到 $(\mathsf{HEto2PC},y_{0},y_{1},x)$时, AS 发送 $T[x]$ 给 RC。 AS 发送 $\sk_{0}$ 给 $\mathcal{F}$， 而RC 发送 $\sk_{1}$ 给 $\mathcal{F}$。 $\mathcal{F}$ 令 $(T[y_{0}],T[y_{1}])=\mathcal{F}^{\mbfvEtoS}(T[x],\sk_{0},\sk_{1})$，并发送 $(\mathsf{HEto2PC},y_{0},x)$ 给 AS，发送 $(\mathsf{HEto2PC},y_{1},x)$ 给 RC。\\
        \textbf{安全两方计算转换到同态加密：} 在接收到 $(\mathsf{2PCtoHE},y,x_{0},x_{1})$时, AS 发送 $\sk_{0}$ 给 $\mathcal{F}$， RC 发送 $\sk_{1}$ 给 $\mathcal{F}$。 $\mathcal{F}$ 令 $T[y]=\mathcal{F}^{\mbfvEtoS}(T[x_{0}],T[x_{1}],\sk_{0},\sk_{1})$，并发送 $(\mathsf{2PCtoHE},y,x_{0},x_{1})$ 给 AS 和 RC。\\
        
        \textbf{安全输出协议：} 在接收到 $(\textsf{安全输出},\mathbf{D},\ct_{res})$时，$\mathcal{F}$ 根据 $\mathbf{D}$ 随机生成 $\mathbf{mask}$， 令 $\ct_{mask}=\ct_{res}\oplus\mathsf{Pack}(\mathbf{mask})$，并发送 $\ct_{mask}$ 给 AS。 AS 发送 $\ct_{mask}$ 给 RC。\\
        AS 发送 $\sk_{0}$ 给 $\mathcal{F}$ 并且 RC 发送 $\sk_{1}$ 给 $\mathcal{F}$。
        $\mathcal{F}$ 令 $\ct'_{res}={\mathcal{F}^{\mbfvPubKeySwitch}}(\ct_{mask},\pk',\sk_{0},\sk_{1})$，并发送 $(\textsf{安全输出},\ct'_{res})$ 给 AS、RC和请求者。\\
        请求者发送 $\sk'$ 给 $\mathcal{F}$。 $\mathcal{F}$ 令 $\hat{m}_{res}={\bfvDec}(\sk',\ct'_{res})$，并且只给请求者发送 $(\textsf{Dec},\hat{m}_{res})$。
        }
    }
    \caption{面向众包数据的隐私保护统计分析框架的理想功能}\label{fig:PSAC_functionality}
\end{figure}


首先考虑请求者被敌手$\mathcal{A}$攻破的情况，因此 RC 也会被敌手$\mathcal{A}$攻破。通过为请求者构建一个模拟器，本研究使用现实/理想世界（real/ideal world）范式提供了严格的证明。只有 AS 被攻破或只有 RC 被攻破的情况的证明是相似的，由于篇幅有限，这里省略了详细的证明。本研究考虑了模拟器中最多有 $K-1$ 个用户和敌手 $\mathcal{A}$ 共谋。


\noindent\textbf{RC和请求者被攻破时的模拟器。} 当得到 RC 和请求者的视图时，模拟器 $\mathcal{S}$ 进行如下操作：

\begin{enumerate}
\item $\mathcal{S}$ 为 AS 生成 $\sk_{0}^{*}$ 并在 $\mbfvEncKeyGen(\sk_{0}^{*},\sk_{1})$ 中模仿 AS 的操作生成 $\cpk^{*}$。
\item 在收到 $(\textsf{安全聚合},k)$时，$\mathcal{S}$ 生成未共谋的用户的 ${\ct}^{*}_{k}=\bfvEnc(\cpk^{*},\hat{m}^{*}_{k})$ 以及 ${CT^{*}_{\textnormal{Sum}}}={\ct}^{*}_{1}\oplus\ldots\oplus{\ct}^{*}_{K}$，其中 $\hat{m}^{*}_{k}$ 打包了随机选择的数据。

\item 在收到 $(\pi,y_{0},S_{\mathsf{in0}})$时，其中 $\pi \in \{\Quantile,\Outlier,\UTest\}$，$\mathcal{S}$ 生成随机秘密共享份额作为 AS 的输入，并模拟 AS 在真实协议 $\pi$ 中的行为。 $\mathcal{S}$ 最后输出RC的秘密共享份额给 $\adversary$。
\item 在收到 $(\pi,y,S_{\mathsf{in}})$时，其中 $\pi\in\{\UTestHE\}$，$\mathcal{S}$ 生成与输入分布相同的随机密文，并模拟 AS 在真实协议 $\pi$ 中的操作。
\item 在收到 $(\mathsf{HEto2PC},y_{0},x)$时，$\mathcal{S}$ 生成与 $T[x]$ 分布相同的随机密文$\ct^{*}$，并将$\ct^{*}$发送给$\adversary$。$\mathcal{S}$ 模拟 AS 在$\mbfvEtoS(\ct^{*},\sk_{0}^{*},\sk_{1})$中的操作。最后，$\mathcal{S}$ 将 RC 的秘密共享份额输出给 $\adversary$。
\item 在收到 $(\mathsf{2PCtoHE},y,x_{0},x_{1})$时，$\mathcal{S}$ 随机生成 $\share{x}_{0}^{*}$ 并模拟 AS 在 $\mbfvStoE(\share{x}_{0}^{*},T[x_{1}],\sk_{0}^{*},\sk_{1})$ 中的行为。 $\mathcal{S}$ 输出密文给 $\adversary$。
\item 在收到 $(\textsf{安全输出},y,\pk'^{*},\mathbf{D},x)$时，$\mathcal{S}$生成一个与$\ct_{res}^{*}$分布相同的随机密文$\ct_{res}$，并根据$\mathbf{D}$生成一个随机的$\mathbf{mask}^{*}$。$\mathcal{S}$ 计算 $\ct_{mask}^{*}=\ct_{res}^{*}\oplus\mathsf{Pack}(\mathbf{mask}^{*})$ 并把 $\ct_{mask}^{*}$ 发送给 $\adversary$。$\mathcal{S}$ 模拟 AS 的操作，和 $\adversary$ 执行 $\ct'^{*}_{res}={\mbfvPubKeySwitch}(\ct_{mask}^{*},\pk'^{*},\sk_{0}^{*},\sk_{1})$ 。最后将 $\ct'^{*}_{res}$ 输出给 $\adversary$。
\end{enumerate}

\noindent\textbf{RC和请求者被攻破时的安全证明。} 本研究通过混合论证（hybrid argument）证明，真实世界的分布与模拟世界的分布是计算不可区分的。
\begin{description}
    \item[$\bullet~\mathsf{Hyb}_{0}$] 这与现实世界中用户数据的分布情况相符。
    \item[$\bullet~\mathsf{Hyb}_{1}$] 在安全聚合阶段替换用户的消息。根据 BFV 方案密文的计算不可区分性，$\mathsf{Hyb}_{1}$ 与 $\mathsf{Hyb}_{0}$ 是不可区分的。
    \item[$\bullet~\mathsf{Hyb}_{2}$] 用模拟的$\pi$来替换$\mathcal{F}^{\pi}$，其中$\pi\in \{\Quantile,\Outlier,\UTest\}$。根据 \Cref{fig:PSAC_functionality_SA_all} 中基于安全两方计算的协议的安全性，$\mathsf{Hyb}_{2}$ 与 $\mathsf{Hyb}_{1}$ 是不可区分的。
    \item[$\bullet~\mathsf{Hyb}_{3}$] 用模拟的输入来替换 $\mathcal{F}^{\pi}$ 的输入，其中 $\pi\in \{\UTestHE\}$。根据 BFV 方案的安全性，$\mathsf{Hyb}_{3}$ 与 $\mathsf{Hyb}_{2}$ 是不可区分的。
    \item[$\bullet~\mathsf{Hyb}_{4}$] 将 $\textsf{HEto2PC},\textsf{2PCtoHE}$ 的输入替换为模拟的输入，并将 $\mathcal{F}^{\mbfvEtoS}$ 和 $\mathcal{F}^{\mbfvStoE}$ 分别替换为模拟的 $\mbfvEtoS$ 和 $\mbfvStoE$。根据 BFV 方案和 MBFV 方案的安全性，$\mathsf{Hyb}_{4}$ 与 $\mathsf{Hyb}_{3}$ 是不可区分的。
    \item[$\bullet~\mathsf{Hyb}_{5}$] 用模拟的 $\ct_{res}^{*}$ 替换输入密文，用模拟的 $\mbfvPubKeySwitch$ 替换 $\mathcal{F}^{\mbfvPubKeySwitch}$ 。根据 BFV 方案和 MBFV 方案的安全性，$\mathsf{Hyb}_{5}$ 与 $\mathsf{Hyb}_{4}$ 是不可区分的。
\end{description}


\noindent\textbf{只有RC被攻破时的模拟器} 可以采用与RC和请求者被攻破时的模拟器类似的过程构建。$\mathcal{S}$ 为请求者生成 $\sk'^{*}$ 和 $\pk'^{*}$ 。最后一步，$\mathcal{S}$ 从敌手 $\mathcal{A}$ 处收到密文 $\ct'^{*}_{res}$。根据BFV方案和MBFV方案的安全性，$\mathsf{Hyb}_{5}$与$\mathsf{Hyb}_{4}$是不可区分的。

\noindent\textbf{AS被攻破时的模拟器} 可以采用与RC被攻破时的模拟器类似的过程构建。$\mathcal{S}$ 为请求者生成 $\sk'^{*}$ 和 $\pk'^{*}$ 。而 $\mathcal{S}$ 将从被攻破的 AS 处接收密文来执行 \textsf{HEto2PC} 协议和 \textsf{SecOutput} 协议。该证明与半诚实威胁模型下 RC 被攻破的情况类似，在此省略详细证明。
\end{proof}


\begin{figure}[htbp]
\centering
\fbox{\parbox{0.96\columnwidth}{
    \small      
    \underline{安全的分位数估计 $\mathcal{F}^{\Quantile}$}:\\
    \textbf{输入：} $p=p'/2^{l'}$，AS:~$\share{\HIST}_{0}\in\mathbb{Z}_{2^l}^{M}$；RC:~$\share{\HIST}_{1}\in\mathbb{Z}_{2^l}^{M}$。\\
    \textbf{输出：} AS:~$\share{Q_{p}}_{0}\in\mathbb{Z}_{2^{l}}$；RC:~$\share{Q_{p}}_{1}\in\mathbb{Z}_{2^{l}}$，其中$Q_{p}$ 是$p$分位数放大倍数为 $2^{l'}$ 的定点数。
            
    \underline{安全的离群值消除 $\mathcal{F}^{\Outlier}$}:\\
    \textbf{输入：} $k=k''/2^{l''}$，AS:~$\share{\HIST}_{0}\in\mathbb{Z}_{2^l}^{M}$，$\share{Q_{3/4}}_{0},\share{Q_{1/4}}_{0}\in\mathbb{Z}_{2^l}$；RC:~$\share{\HIST}_{1}\in\mathbb{Z}_{2^l}^{M}$，$\share{Q_{3/4}}_{1}, \share{Q_{1/4}}_{1}\in\mathbb{Z}_{2^l}$，其中 $Q_{3/4}$ 和 $Q_{1/4}$ 被放大 $2^{l'}$ 倍。\\
    \textbf{输出：} AS:~$\share{\HIST^{*}}_{0}\in\mathbb{Z}_{2^{l}}^{M}$；RC:~$\share{\HIST^{*}}_{1}\in\mathbb{Z}_{2^{l}}^{M}$，其中 $\HIST^{*}=\left[F^{*}_{1},F^{*}_{2},\ldots,F^{*}_{M}\right]$，并且当 $s_{i}>(Q_{3/4}+k\cdot\text{IQR}) \vee s_{i}<(Q_{1/4}-k\cdot\text{IQR})$ 时 $F^{*}_{i}=0$，否则 $F^{*}_{i}=F_{i}$。

    \underline{安全的曼-惠特尼\textit{U}检验 $\mathcal{F}^{\UTest}$}:\\
    \textbf{输入：} AS:~$\share{\HIST_{X}}_{0},\share{\HIST_{Y}}_{0}\in\mathbb{Z}_{2^l}^{M}$；RC:~$\share{\HIST_{X}}_{1},\share{\HIST_{Y}}_{1}\in\mathbb{Z}_{2^l}^{M}$。\\
    \textbf{输出：} AS:~$\share{U_{X}}_{0},\share{U_{Y}}_{0}\in\mathbb{Z}_{2^{l}}$；RC:~$\share{U_{X}}_{1},\share{U_{Y}}_{1}\in\mathbb{Z}_{2^{l}}$，其中 $U_{X}$ 和 $U_{Y}$ 是放大了 $2$ 倍的定点数。
    }
}
\caption{基于安全两方计算的统计分析协议的理想功能}\label{fig:PSAC_functionality_SA_all}
\end{figure}


\begin{theorem}
协议 $\protocol{\Quantile}$、$\protocol{\Outlier}$ 和 $\protocol{\UTest}$ 分别安全地实现了\Cref{fig:PSAC_functionality_SA_all} 中的安全功能 $\mathcal{F}^{\Quantile}$、$\mathcal{F}^{\Outlier}$ 和 $\mathcal{F}^{\UTest}$。
\end{theorem}

\begin{proof}
这些协议是本地计算和调用 $\mathcal{F}^{\Equal}$、$\mathcal{F}^{\Less}$、$\mathcal{F}^{\LessOrEqual}$、$\mathcal{F}^{\Multiply}$、$\mathcal{F}^{\Trunc}$、$\mathcal{F}^{\Mux}$ 和 $\mathcal{F}^{\BtoA}$ 的顺序组合，$\mathcal{F}^{\Quantile}$、$\mathcal{F}^{\Outlier}$ 和 $\mathcal{F}^{\UTest}$ 的模拟器直接来自于这些子安全功能的模拟器的组合。根据顺序组合定理（Sequential Composition Theorem），这些协议是安全的。
\end{proof}

\section{性能分析与实验验证}

本节将分析和评估本方案所提出的框架和协议的性能。在\Cref{subsection:PSAC_Experiment_Setup}中将详细介绍实验设置。在\Cref{subsection:PSAC_Performance_Framework}中分析了框架主要设计的开销，包括安全聚合阶段的开销和与密钥分离设计相关的协议。然后，在\Cref{subsection:PSAC_Cost_Analysis}和\Cref{subsection:PSAC_Performance_Statistic}中，分析并评估了本方案提出的使用直方图的统计分析协议的性能。本实验主要将分位数估计协议与Lu等人~\cite{lu2017using}和Bogdanov等人~\cite{bogdanov2018rmind}的设计进行比较。通过性能比较和评估，实验展示了本方案的协议的高效性和对于数据点数量的可扩展性，以及本方案框架设计的优势。



\subsection{实验设置}\label{subsection:PSAC_Experiment_Setup}

\textbf{框架实现。} 本实验使用 lattigo~\cite{lattigo} 和 SCI~\cite{rathee2020cryptflow2,rathee2021sirnn} 库作为安全计算后端，构建了本方案的框架。lattigo 库提供了框架中使用的 MBFV 方案。SCI 库是一个安全的两方计算库，实现了本方案设计需要的基于不经意传输的协议和实验对比需要的基于混淆电路的协议。实验设置了安全参数 $\lambda=128$。

\textbf{实验环境。} 性能测试是在配备 2.10GHz Intel Xeon Gold 6230R CPU 和 32GB 内存的服务器上，在模拟的广域网（带宽 200Mbps，延迟 20ms）和局域网（带宽 2500Mbps，延迟 1ms）环境下进行的。

\textbf{符号表示。} 本节假设用户数量为 $K$，所有用户上传的数据点的总数为 $P$，每个数据点的取值空间大小为 $M$。

\subsection{框架主要设计的性能}\label{subsection:PSAC_Performance_Framework}

\subsubsection{安全聚合协议的性能}


本实验分析了\Cref{subsec:PSAC_secure_agg}中安全向量聚合协议的开销，从中也可以直接得到安全直方图聚合协议的开销。

令 $M'$ 是向量的长度，$L$ 是每个密文中打包的子向量的长度，且 $L\le n$，$S_{\ct}$ 是密文的大小，那么加密数据向量所需的密文数为 $n_{\ct}=\lceil M'/L\rceil$ 。本节使用 $T^{*}$ 表示协议或操作的计算开销 $\protocol{*}$。对于每个\textbf{用户}，计算开销为 $n_{\ct}$，其中$K$是用户个数，$T^{\Enc}_{n}$ 是使用公钥加密的计算开销，而通信开销是 $n_{\ct}S_{\ct}$。至于 \textbf{AS}，要对所有用户的密文求和，计算开销为 $(K-1) n_{\ct} T^{\CAdd}$，其中，$T^{\CAdd}_{n}$ 是两个密文相加的计算开销，通信开销是 $K n_{\ct} S_{\ct}$。\textbf{RC}不参与安全聚合阶段。由于聚合协议的性能与 $K$ 和 $n_{\ct}$ 有关，实验可以通过评估 BFV 方案的开销来估算聚合协议的开销。

本实验将 BFV 方案的 $n$ 分别设置为 2048、4096 和 8192，并使用 lattigo 提供的默认参数，这些参数至少提供了 128 位的安全级别。\Cref{table:BFV_overhead} 中展示了验证结果。$Q_{0}$ 是 lattigo 实现中的一个参数，也是参数集支持的最大明文模数。

\begin{table}[htb]
    \caption{BFV方案的开销（每个密文）}\label{table:BFV_overhead}
    \centering
    \resizebox{0.8\columnwidth}{!}{
    \begin{tabular}{ccccccc}
            \toprule
            参数 & $n$  & $Q_{0}$  & $T^{\Enc}_{n}$ (ms) & $T^{\Dec}_{n}$ (ms)& $T^{\CAdd}_{n}$ (us) & $S_{\ct}$ (KB) \\
            \midrule
            PN11QP54   & 2048 & 12289 & 0.351    & 0.096   & 5.81    & 64                   \\
            PN12QP109  & 4096 & 549755731969 & 1.166    & 0.323   & 31.5    & 128                  \\
            PN13QP218  & 8192 & 18014398508400641 & 3.373    & 1.210   & 146     & 384                  \\
            \bottomrule
    \end{tabular}
    }
\end{table}


一般来说，BFV 方案的性能受参数集的影响很大，而明文模$t$的选择对性能影响不大。实际中可以在保证 $t>P$ 的前提下，关注于选择较小的参数集，并将一个数据向量拆分到多个密文中，这将有助于减小密文的大小，提高聚合阶段的效率。这里以一个典型的众包场景为例估算开销。当数据点数量 $P=40000$，从 $K=20$ 个用户处采集，取值空间大小 $M=8000$时，直方图聚合不能使用参数 PN11QP54，因为 $P>Q_{0}$。实际中可以选择 PN12QP109，其中一个密文有 $n=4096$ 个密文插槽，这样可以选择 $L=4000$。每个用户需要 $n_{\ct}=2$ 个密文，大小为 $2S_{\ct}=256$ KB。AS 聚合这些密文的计算开销和通信开销分别为 $19\times 2\times 31.5=1197.0$ us 和 $20\times 2\times 128=5120$ KB。当选择 PN13QP218 时，每个用户只需要一个大小为 384 KB 的密文。AS 的计算和通信开销分别为 $2774$ ms 和 $7680$ KB。对于直方图聚合，选择较小的参数会降低开销。直方图聚合过程的开销与用户数量成线性关系。不过，由于计算过程是一个简单的累加过程，因此当用户上传数据时，服务端能用可接受的开销快速完成计算。而且这样的聚合过程只需执行一次。


\subsubsection{密钥分离设计相关协议的性能} 

为了实现密钥分离设计，基于 MBFV 方案~\cite{mouchet2021multiparty}，本实验使用 $\mbfvEtoS$ 和 $\mbfvStoE$ 实现了在\Cref{subsec:PSAC_statistical_phase}中的同态加密和安全两方计算之间的转换的协议 $\protocol{\mathsf{HEto2PC}}$ 和 $\protocol{\mathsf{2PCtoHE}}$，以及在\Cref{subsec:PSAC_output}的安全输出阶段中使用 $\mbfvPubKeySwitch$ 来实现密文的公钥转换。\Cref{table:MBFV_overhead} 展示了这些协议在处理一个密文时的性能。其中，计算开销是 AS 和 RC 上的总计算时间。对于 $\protocol{\mathsf{HEto2PC}}$ 和 $\protocol{\mathsf{2PCtoHE}}$ 来说，通信开销是 AS 从 RC 收到的多项式秘密共享份额的大小。至于 $\protocol{\mathsf{SecOutput}}$，通信开销是 RC 从 AS 处接收的密文份额的大小。最后，请求者需要解密结果的密文，计算开销 $T^{\Dec}_{n}$ 也在\Cref{table:BFV_overhead} 中给出。


\begin{table}[htb]
\caption{密钥分离设计相关协议中AS和RC的开销（每个密文）}\label{table:MBFV_overhead}
\centering
\resizebox{0.8\columnwidth}{!}{
\begin{tabular}{ccccccc}
\toprule
\multirow{2}{*}{参数} 
& \multicolumn{2}{c}{${\mathsf{HEto2PC}}$} 
& \multicolumn{2}{c}{${\mathsf{2PCtoHE}}$}
& \multicolumn{2}{c}{${\mathsf{SecOutput}}$} \\
& 计算 (ms) & 通信 (KB) & 计算 (ms) & 通信 (KB) & 计算 (ms) & 通信 (KB) \\
\midrule
PN11QP54   & 0.254 &  32  & 0.188 & 32  & 0.428 & 64  \\
PN12QP109  & 0.950 &  64  & 0.461 & 64  & 1.676 & 128 \\
PN13QP218  & 2.816 &  192 & 1.766 & 192 & 4.926 & 384 \\
\bottomrule
\end{tabular}
}
\end{table}

以 $M=8000$ 为例，本实验使用参数 PN12QP109，然后将一个直方图打包成 $n_{\ct}=2$ 个密文。那么 AS 和 RC 执行一次 $\protocol{\mathsf{SecOutput}}$ 的计算时间接近 $1.676\times 2=3.352$ ms，AS 需要向 RC 发送总计 $256$ KB 的秘密共享份额的消息。RC 向请求者发送 $n_{\ct}=2$ 个密文，共$256$ KB。请求者需要花费 $2\times 0.323=0.646$ ms 来解密结果。

对于直方图或分析结果的每个向量，最多需要执行一次同态加密的密文与秘密共享之间的转换或输出密文的公钥转换。与基于安全两方计算的统计分析协议相比，这些协议的开销要小得多。如果研究计划不需要在同态密文和秘密共享之间进行转换，则只需输出密文公钥转换的开销。

\subsection{实用直方图的统计分析协议的复杂度分析}\label{subsection:PSAC_Cost_Analysis}

在\Cref{subsec:vectorized_2pc}中，介绍了本方案所需要各个向量化算子的理想功能 $\mathcal{F}_{*}$。它们基于不经意传输的安全两方计算协议来自~\cite{rathee2020cryptflow2,rathee2021sirnn}，本论文在\Cref{section:preliminaties_mpc}中介绍。
本小节用 $C_{*}$ 表示这些协议计算单个元素的通信开销，用 $R_{*}$ 表示执行协议所需要的交互轮数，其中下标 $*$ 表示每个协议的参数。这些协议具体的通信开销和交互轮数见\Cref{table:PSAC_OT_protocols}。

\begin{table}[htb]
    \centering
    \caption{基于不经意传输的安全两方计算协议的开销}\label{table:PSAC_OT_protocols}
    \centering
    \resizebox{0.6\linewidth}{!}{
    \begin{tabular}{cccc}
    \toprule
    理想功能 & 协议 & 通信开销 (bits) & 交互轮数 \\
    \midrule
    $\mathcal{F}^{\Less}_{l},\mathcal{F}^{\LessOrEqual}_{l}$
    & $\Less,\LessOrEqual$
    & $<\lambda l+14l$
    & $\log(l)$ \\
    $\mathcal{F}^{\Multiply}_{l}$
    & $\Multiply$
    & $l(\lambda+\frac{l+1}{2})$
    & $2$ \\
    $\mathcal{F}^{\Trunc}_{l,l'}$
    & $\Trunc$
    & $\lambda(l' + 1) + l + 13l'$
    & $\log(l')$ \\
    $\mathcal{F}^{\Mux}_{l}$
    & $\Mux$
    & $2(\lambda + l)$
    & $2$ \\
    $\mathcal{F}^{\BtoA}_{l}$
    & $\BtoA$
    & $\lambda + l$
    & $2$ \\
    \bottomrule
    \end{tabular}
    }
\end{table}

对于每个统计分析协议，可以根据调用的各个算子来分析开销，如\Cref{table:overhead_protocols} 所示。$M$ 和 $l$ 是直方图向量的长度（取值空间大小）和秘密共享的位宽，$P$是数据点的总数，$2^{l'}$ 是分位数估计中 $p$ 的缩放因子。此外，当直方图表示的数据点数量在协议 $\protocol{\Quantile}$ 中保密时，会引入执行 $\protocol{\Trunc}$ 的开销。本小节计算了分位数估计、离群值消除和曼-惠特尼\textit{U}检验的基于安全两方计算的协议$\protocol{\Quantile}$、$\protocol{\Outlier}$和$\protocol{\UTest}$的交互轮数，分别是$\log(l')+\log(l-l')+4$、$\log(l)+2$和$2$。正如在\Cref{subsec:PSAC_statistical_phase}中对每个协议的正确性分析所解释的那样，实际中需要足够大的 $l$ 来保证不发生溢出。
由于本方案的算法包括直方图和数值型数据计算，因此 $l$ 和 $P$、$M$ 仅仅是对数相关的。如果尽可能选择适当小的 $l$，那么交互轮数就并不会随着 $P$ 和 $M$ 的增加而大幅增加。此外，假设固定一个足够大的数据位宽 $l$，协议的通信开销就只会随着 $M$ 的增加而接近线性增长，而与数据点数量无关。因此，使用直方图的协议的效率更多地受到取值空间大小$M$的影响。

\begin{table}[htb]
    \centering
    \caption{使用直方图的统计分析协议的开销分析}\label{table:overhead_protocols}
    \centering
    \resizebox{\linewidth}{!}{
    \begin{tabular}{ccc}
    \toprule
    协议 & 通信开销 & 交互轮数 \\
    \midrule
    分位数估计
    & $(C^{\Trunc}_{l,l'})+M\cdot C^{\LessOrEqual}_{l-l'}+M\cdot C^{\BtoA}_{l}+C^{\Multiply}_{l}$
    & $(R^{\Trunc}_{l,l'})+R^{\LessOrEqual}_{l-l'}+R^{\BtoA}_{l}+R^{\Multiply}_{l}$ \\
    离群值消除
    & $2M\cdot C^{\Less}_{l}+M\cdot C^{\Mux}_{l}$
    & $R^{\Less}_{l}+R^{\Mux}_{l}$ \\
    曼-惠特尼\textit{U}检验
    & $2M\cdot C^{\Multiply}_{l}$
    & $R^{\Multiply}_{l}$ \\
    \bottomrule
    \end{tabular}%
    }
\end{table}

至于\Cref{subsec:PSAC_mann_whitney_u_test}中基于同态加密的安全曼-惠特尼\textit{U}检验协议 $\protocol{\UTestHE}$，计算仅由 AS 完成，不需要任何交互通信。计算开销为 $2 (T^{\PMul}+T^{\CMul}+T^{\PAdd})$，其中 $\PAdd$ 和 $\PMul$ 分别是密文和明文之间的加法运算和乘法运算，$\CMul$ 是两个密文的乘法运算。

\subsection{使用直方图的统计分析协议的性能}\label{subsection:PSAC_Performance_Statistic}

\subsubsection{对比的基准方案选择}

为了说明本方案的协议在数据点数量方面的可扩展性优势，本实验选择分位数估计协议作为典型设计，并将其与其他工作中的设计进行比较。在不知道直方图所代表的数据点数量 $P'$ 的情况下，设置 $p=1/4$ 和 $l'=2$，计算现实中常用的四分位数 $Q_{1/4}$。本实验选择对比的基准方案如下：


\textbf{与使用数值型数据的协议进行比较。} 
本实验主要将安全统计分析算法的设计与Rmind中的算法进行比较~\cite{bogdanov2018rmind}。
Rmind 是当前所知的最高效的基于 MPC 的加密安全统计分析工具之一，它提供了多种使用数值型数据的协议，包括分位数估计和曼-惠特尼\textit{U}检验等。然而，Rmind 中使用数值型数据的这两个协议都需要安全排序算法。在本方案的安全两方计算设置中，这种安全排序算法占据了主要开销。为了减少广域网中网络延迟造成的性能下降，本实验使用了一种高度并行的排序网络算法，它也提供在实现Rmind的安全三方计算框架Sharemind~\cite{bogdanov2008sharemind}中。本实验主要比较了保护直方图中数据点数量 $P'$ 的分位数估计协议，以说明本方案的协议在数据点总量方面的可扩展性优势。曼-惠特尼\textit{U}检验的性质类似，因此本实验省略了相关比较。

\textbf{不同安全计算技术实现的协议比较。}
为了验证特定安全计算技术对协议效率的影响，本实验还使用另一种常见的安全两方计算技术——混淆电路（GC）实现了本方案的算法和 Rmind 中的算法，并与本方案选择的使用不经意传输的实现进行了比较，从而反映出本方案的协议在使用对向量化操作更友好的安全计算技术时的效率优势。至于基于同态加密的协议，Lu 等人~\cite{lu2017using} 提供了一个 $k$-百分位数协议，它与本方案的分位数估计函数类似，使用了BGV同态加密方案~\cite{brakerski2014leveled}和相似的指标编码。为了进行比较，本实验也在本方案提出的框架中实现了它。


性能对比结果如\Cref{fig:QE_performance}所示。从图中灰色线条可以看出本方案的算法设计和协议具体实现的性能优势。当数据点个数的数量级增长时，本方案的协议开销增长并不明显。并且不论在局域网还是广域网下，本方案的协议都几乎是最高效的。因此，本方案的算法对于数据点的数量具有良好的可扩展性。而且本方案尽可能减少了算法的迭代次数，并充分利用了向量化操作，这使得基于不经意传输的协议实现在本方案的框架中更具优势。



\subsubsection{安全的分位数估计协议的性能对比}

首先关注协议在用户所上传的数据点数量方面的可扩展性。本实验设置了固定的 $M=4000$，它提供了约 $12$ 比特的精度，允许使用参数 PN12QP109 将直方图向量打包成具有 $4096$ 个插槽的密文。本实验将数据点的数量设置为从 $100$ 到 $40000$ 的不同数量级，这样会使直方图向量中各元素的位宽 $l$ 逐渐增加，以测试在局域网和广域网环境中的通信开销和运行时间。\Cref{fig:QE_performance}展示了比较结果，其中\Cref{fig:QE_communication} 展示了 AS 和 RC 之间的通信开销，\Cref{fig:QE_computing_lan,fig:QE_computing_wan} 分别展现了整个协议在局域网和广域网中的运行时间。

\begin{figure}[ht]
    \centering
    \subcaptionbox{通信开销\label{fig:QE_communication}}{
            \includegraphics[width=0.48\linewidth]{figures/PSAC_quantile_communication_line.pdf}
    }
    \subcaptionbox{协议执行时间 (局域网)\label{fig:QE_computing_lan}}{
            \includegraphics[width=0.48\linewidth]{figures/PSAC_quantile_computation_lan.pdf}
    }\\
    \subcaptionbox{协议执行时间 (广域网)\label{fig:QE_computing_wan}}{
            \includegraphics[width=0.48\linewidth]{figures/PSAC_quantile_computation_wan.pdf}
    }
    \caption{安全的分位数估计协议的性能对比 (取值空间大小 $M$ 设置为 4000， 数据点个数 $P$ 从 100 到 40000)。}\label{fig:QE_performance}
\end{figure}

从整体趋势来看，当 $M$ 固定时，随着 $P$ 的增加，本方案的协议在局域网和广域网下的通信开销和运行时间增长非常平缓，这表明本方案的协议对数据点数量并不敏感。这与\Cref{subsection:PSAC_Cost_Analysis}中对本方案算法的理论开销分析是一致的。对于 Rmind 中使用安全排序算法的协议和 Lu 等人~\cite{lu2017using} 提出的基于同态加密的协议，开销会随着数据点数量的增加而增加。安全排序网络算法需要 $t(t+1)/2$ 轮并行比较操作，其中 $t=\lceil\log(P)\rceil$，每轮的规模为 $P/2$。因此，随着 $P$ 的增加，通信开销和交互轮数将大幅增加，导致运行时间显著增加。

至于Lu 等人基于同态加密的协议~\cite{lu2017using}，虽然也采用了指标编码并利用了向量化的操作，但它受限于同态加密方案在整数计算方面的能力，需要多次复制密文才能实现比较操作，因此计算复杂度和密文大小都是 $O(PM)$ 的。为了解密和重构出统计结果，请求者必须从服务器接收密文，这也导致了巨大的通信开销。这使得随着 $P$ 的增加，Lu 等人提出的协议~\cite{lu2017using}开销增长最快。更优的基于同态加密的比较协议可能有助于减少这种代价高昂的密文复制。然而，对于本方案的框架来说，最实用的协议仍然是基于安全两方计算的，这样的协议广泛应用于具有大量向量化操作的加密神经网络推理~\cite{juvekar2018gazelle,rathee2020cryptflow2,rathee2021sirnn}。

就具体性能而言，对于本方案提出的使用直方图的协议，基于不经意传输的实现在局域网和广域网中的通信开销和运行时间分别为 $1.0\pm 0.1$ MB、$43.5\pm 4.4$ ms 和 $436.8\pm 24.3$ ms。相比之下，基于混淆电路的实现需要 $19.2\pm 3.0$ MB、$135.0\pm 31.0$ ms 以及 $1446.5\pm 135.5$ ms。在局域网和广域网中，基于不经意传输实现的协议的通信开销和运行时间明显低于基于混淆电路实现的协议。

至于在Rmind中使用数值型数据的协议，基于不经意传输协议的实现的通信开销、在局域网和广域网中的运行时间分别为 $0.59\sim 681.39$ MB、$481\sim 17990$ ms 和 $5297\sim 57936$ ms，而基于混淆电路的实现的通信开销、在局域网和广域网中的运行时间分别为 $1.62\sim 2109.18$ MB、$53\sim 8899$ ms 和 $518\sim 93302$ ms。虽然基于不经意传输实现的通信开销总是低于基于混淆电路实现的通信开销，但当数据点数量较少时，由于基于混淆电路的实现可以在恒定的轮数内完成排序，因此基于不经意传输实现的协议的运行时间要明显高于基于混淆电路的实现的运行时间，这是因为排序的交互轮数较多。但是，随着数据点数量的不断增加，排序的电路也会显著增大，受限的带宽对效率的影响逐渐增大。当 $P=40000$ 时，广域网中基于不经意传输的实现效率会高于基于混淆电路的实现效率。

对\Cref{fig:QE_performance} 的分析体现了本方案的算法设计和协议具体实现的性能优势。本方案的算法对于数据点的数量具有良好的可扩展性，而且尽可能减少了算法的迭代次数，并充分利用了向量化操作，这使得基于不经意传输的实现在本方案的框架中更具优势。


\subsubsection{其他协议}

在这一部分，实验将评估本方案的分位数估计协议和其他功能的性能，包括离群值消除和曼-惠特尼\textit{U}检验。至于\Cref{subsec:chi2_test} 中构建列联表的方法，除了安全直方图聚合和执行 $\mathsf{HEto2PC}$ 协议外，所有操作都是在本地秘密共享上进行的，成本几乎为零。因此，本实验省略了对其性能的分析。在此重点分析广域网环境下的运行时间和通信开销，这更接近实际使用情况。对于离群值消除，本实验首先使用分位数估计协议计算 $Q_{3/4}$ 和 $Q_{1/4}$，然后将结果输入离群值消除协议。这里设置 $k=1/4$ 和 $l''=2$。在避免溢出的前提下，尽可能地选择更小的位宽 $l$。

1）对于不同数据点数量下的协议性能，实验设置固定的 $M=4000$，并选择与\Cref{fig:QE_performance} 中相同的数据点数量来测试运行时间和通信开销。假设每个数据点的取值空间为 $[1,4000]$。\Cref{table:performance_fixed_M} 展示了本方案协议的性能。

\begin{table}[ht]
    \caption{本方案提出的协议在不同数据点数量下的性能}\label{table:performance_fixed_M}
    \centering
    
    \resizebox{\linewidth}{!}{
    \begin{tabular}{@{\extracolsep{\fill}}cc cccccc}
    \toprule
    \multirow{2}{*}{性能指标}& \multirow{2}{*}{协议} & \multicolumn{6}{c}{$P$}\\ \cmidrule{3-8}& & 100 & 400 & 1000 & 4000 & 10000 & 40000 \\ \midrule
\multirow{4}{*}{执行时间 (ms)}
    & 分位数估计                    & 412.4 & 413.3 & 414.6 & 416.9 & 461.1 & 469.9 \\
    & 离群值消除                    & 329.4 & 329.4 & 329.7 & 329.3 & 335.7 & 335.8 \\
    & 曼-惠特尼\textit{U}检验            & 715.5 & 746.9 & 864.9 & 938.0 & 1064.4 & 1104.8 \\
    & 曼-惠特尼\textit{U}检验（同态加密）  & 33.3 & 33.3 & 33.3 & 33.3 & 33.3  & 33.3  \\\midrule
\multirow{3}{*}{通信开销 (MB)}
    & 分位数估计                & 0.85 & 0.85 & 0.85 & 0.85 & 1.12 & 1.13 \\
    & 离群值消除                & 2.265 & 2.265 & 2.265 & 2.265 & 2.266 & 2.268 \\
    & 曼-惠特尼\textit{U}检验       & 8.92 & 9.16 & 11.37 & 11.68 & 13.92 & 14.29 \\
    \bottomrule
\end{tabular}
    }
\end{table}

对于分位数估计和离群值消除协议，当 $P\le 4000$ 时，由于位宽 $l$ 的选择主要受取值空间的影响，其中 $s_{M}=4000$ 是固定的，因此本方案的协议的开销几乎没有变化。当 $P>4000$ 时，$l$ 的选择主要由 $P$ 决定，$l$ 会随着 $P$ 的数量级逐渐增大，导致开销略有增加。至于曼-惠特尼\textit{U}检验，$l$ 的选择受 $P$ 和 $M$ 的对数影响，因此即使 $M$ 固定不变，该协议的通信费用也会随着 $P$ 的增加而略有增加，从而导致运行时间略有增加。由于这些协议的开销主要与 $l$ 有关，因此开销的增加也非常平缓。

特别地，本方案基于同态加密的曼-惠特尼\textit{U}检验的协议比基于安全两方计算的协议要快得多。基于同态加密的协议的计算开销几乎不变，因为直方图的长度被固定为 $M=4000$，而 BFV 方案的参数 $n$ 也被固定为 $8192$，以确保计算的正确性。由于算法只包括加法和乘法，因此可以利用同态加密的优势，协议运行时间非常短，而且无需交互。


2）由于本方案协议的开销对 $P$ 的增加并不敏感，因此在实际使用中，将更关注取值空间大小变化时的性能。本实验还测试了当数据点数量 $P$ 固定为 $4000$，取值空间的大小 $M$ 从 $100$ 到 $40000$ 变化时协议的性能。假设 $s_{1}=1$，这样 $s_{M}=M$。结果展示在 \Cref{table:performance_fixed_P} 中。

\begin{table}[ht]
    \caption{本方案提出的协议在不同数据点取值空间下的性能}\label{table:performance_fixed_P}
    \centering
    \resizebox{\linewidth}{!}{
    \begin{tabular}{@{\extracolsep{\fill}}cc cccccc}
    \toprule
    \multirow{2}{*}{性能指标} & \multirow{2}{*}{协议} & \multicolumn{6}{c}{$M$} \\
    \cmidrule{3-8}
    &                            & 100 & 400 & 1000 & 4000 & 10000 & 40000 \\ \midrule
    \multirow{4}{*}{执行时间 (ms)}
    & 分位数估计                     & 339.7 & 341.2 & 347.3 & 413.7 & 649.9 & 1253.8 \\
    & 离群值消除                     & 174.5 & 179.1 & 192.9 & 333.6 & 575.7 & 1518.2 \\
    & 曼-惠特尼\textit{U}检验             & 129.7 & 215.7 & 454.6 & 811.1 & 1357.8 & 4807.4 \\
    & 曼-惠特尼\textit{U}检验（同态加密） & 10.0 & 10.0 & 10.0 & 33.3 & 662.2  & --- \\\midrule

    \multirow{3}{*}{通信开销 (MB)}
    & 分位数估计          & 0.05 & 0.11 & 0.23 & 0.85 & 2.95 & 11.93 \\
    & 离群值消除          & 0.100 & 0.243 & 0.460 & 2.265 & 6.511 & 30.626 \\
    & 曼-惠特尼\textit{U}检验  & 0.25 & 1.02 & 4.38 & 11.68 & 28.39 & 121.23 \\

    \bottomrule
    \end{tabular}
    }
\end{table}


至于分位数估计和离群值消除协议，当 $M\le P$ 时，$l$ 几乎是固定的；当 $M> P$ 时，$l$ 的选择主要由 $M$ 决定。虽然增加 $l$ 可能会增加交互轮数，但影响不大。由于 $M$ 的增加而导致的通信开销的增加对运行时间的影响更大。至于曼-惠特尼\textit{U}检验协议，交互轮数是固定的，运行时间受通信开销的影响，而通信开销随 $M$ 的增加而显著增加。总之，网络延迟和通信开销会影响这些协议的运行时间，随着 $M$ 的增加，通信开销的影响更加明显。

至于基于同态加密的曼-惠特尼\textit{U}检验协议，当 $M<1000$ 时，设置 $n=4096$ 以提供足够大的明文模数。此外，当 $M=4000$ 和 $10000$ 时，分别设置 $n=8192$ 和 $32768$，以确保正确性。对于 $M=40000$，无法找到一个合适的默认参数来提供足够大的 $n>2M$。基于同态加密的协议的计算开销主要与同态加密的参数有关。然而，过大的参数会大大降低计算效率。在实际应用中，应根据 $M$ 的大小选择合适的技术来实现算法。这也体现了本方案的框架同时支持基于同态加密和安全两方计算的协议的设计的优势，它提供了选择的可能性。

总之，本方案的协议更适合取值空间较小的统计应用。对于大多数实际应用而言，将取值空间大小设定为 $100$ 到 $40000$ 足以覆盖大多数统计分析任务。在广域网中，每个统计分析函数的在线计算时间从几百毫秒到几秒不等，这对于众包来说是可以接受的。在取值空间较大的情况下，可以考虑数据量化以降低开销。尽管如此，在处理用户上传的大量数据点时，本方案提出的新的协议的性能和可扩展性都非常出色。这就是本方案的框架包括直方图和数值型数据的原因，因为这样可以获得更广泛的适用性。


\section{本章小结}

在这项工作中，本方案提出了一个面向大规模众包数据的隐私保护统计分析框架，它可以实现加密安全的统计分析。本方案提出的框架结合了同态加密和安全两方计算协议，允许组合不同的统计分析安全协议完成复杂的任务。密钥分离的设计解决了单一密钥带来的隐私风险。此外，本方案设计的使用直方图的新型统计分析协议对用户上传数据点的总数具有良好的可扩展性。理论分析和性能评估表明，本方案的框架安全高效，在处理大规模数据时优势突出。在未来的工作中，可以考虑用更多的统计分析协议来扩展本方案，以增强其功能，并探索为框架提供输出隐私扩展的方法。